Score:1

การทำงานอัลกอริทึม Coppersmith หลายตัวแปร

ธง cn

ฉันเพิ่งศึกษาอัลกอริทึม Coppersmith หลายตัวแปร อนุญาต $ฉ(x)$ เป็น $n$- แปรผันพหุนามมากกว่า $\mathbb{Z}_p$ สำหรับนายกรัฐมนตรีบางคน $p$. อย่างไม่เป็นทางการ ทฤษฎีบทของ Coppersmith หลายตัวแปรระบุว่าหากสมมติฐาน ($*$) ค้างไว้ จากนั้นเราสามารถแก้อัลกอริทึมของ Coppersmith หลายตัวแปรในเวลาพหุนามในพารามิเตอร์บางตัว

($*$): มีอยู่ $n$ พหุนามอิสระเชิงพีชคณิตที่ได้จากอัลกอริทึม LLL บนเมทริกซ์ $M$โดยที่แต่ละแถวของ $M$ เป็นเวกเตอร์สัมประสิทธิ์ของการคูณของ $f$ หรือ $p$.

ในที่นี้ เพื่อความสะดวกในการนำเสนอ ข้าพเจ้าถือว่าเกณฑ์ของ Coppersmith ยึดถือเสมอ

คำถามของฉันคือ: ถ้า $n$ มีขนาดใหญ่ (เช่น n = 50 หรือ 100) แล้วเราจะหาได้ไหม $n$ พหุนามอิสระเชิงพีชคณิตจาก $M$? ฉันคิดว่ามันเป็นไปไม่ได้เสมอตั้งแต่นั้นมา $n$ ใหญ่เกินไป แต่ฉันไม่พบกระดาษที่เกี่ยวข้องกับขนาดใหญ่ดังกล่าว $n$.

** ฉันรู้ว่าความซับซ้อนในการค้นหาพหุนามหลายตัวแปรนั้นมีค่าใช้จ่ายสูง แต่ในหัวข้อนี้ ฉันเน้นเฉพาะการมีอยู่ของ $n$ พหุนามอิสระเชิงพีชคณิต

มีตัวอย่างใดบ้างสำหรับการใช้อัลกอริทึมของ Coppersmith หลายตัวแปรสำหรับ $n>5$? ฉันพบเฉพาะแอปพลิเคชันของอัลกอริทึมของ Coppersmith หลายตัวแปรในพหุนามเท่านั้น $n = 2$ หรือ $3$. ดังนั้นฉันค่อนข้างสับสนว่าอัลกอริทึมของ Coppersmith สามารถทำงานได้จริงหรือไม่ $n>5$. อันที่จริงฉันไม่รู้ว่าจะได้รับอย่างไร $n$ พหุนามอิสระเชิงพีชคณิตจากพหุนามเดียว $f$.

นอกจากนี้ วิธีการรับประกันสมมติฐาน ($*$) สำหรับบางคน $n = 10,20,30$? ฉันคิดว่ามันยากที่จะใช้กรณีดังกล่าวในคอมพิวเตอร์ส่วนบุคคล ในกรณีนี้จะโน้มน้าวใจได้อย่างไรว่าอัลกอริทึมสำเร็จ

Turbo avatar
ru flag
คุณหา $n=3$ ได้ที่ไหน

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา