Score:-2

เลขคณิตโมดูลาร์ที่ตรงไปตรงมาสำหรับโมดูลัสยกกำลังสอง

ธง in

ทำไมถ้า $คิว$ เป็นจำนวนเต็มยกกำลังสองแล้วทำโมดูโลเลขคณิต $คิว$ (การบวกและการคูณ) มีประสิทธิภาพและตรงไปตรงมามาก?

forest avatar
vn flag
ฉันลงคะแนนให้ปิดคำถามนี้ เนื่องจากเป็นคำถามเกี่ยวกับประสิทธิภาพของการดำเนินการทางคณิตศาสตร์อย่างง่ายในคอมพิวเตอร์ และไม่เฉพาะเจาะจงสำหรับการเข้ารหัส
Mark avatar
ng flag
สิ่งที่ควรค่าแก่การกล่าวถึงสิ่งนี้อาจเกี่ยวข้องกับการเข้ารหัส --- ข้อแตกต่าง (สำคัญ) อย่างหนึ่งระหว่าง Saber ผู้เข้ารอบสุดท้ายของ NIST PQC และ Kyber คือ Saber มีโมดูลาร์แบบยกกำลังสอง $2^{13}$ (และการลดโมดูลาร์ที่รวดเร็ว) ในขณะที่ Kyber ใช้โมดูลิที่เป็นมิตรกับ NTT ซึ่งยอมรับอัลกอริทึมการคูณที่มีประสิทธิภาพมากกว่า (แต่ซับซ้อนกว่า) สิ่งนี้นำไปสู่การวิจัยการเข้ารหัสเปรียบเทียบทั้งสอง และแม้แต่การค้นหาวิธีฝังการคูณแบบยกกำลังสองลงในวงแหวนที่เป็นมิตรของ NTT
Score:3
ธง my

ทำไมถ้า $คิว$ เป็นจำนวนเต็มยกกำลังสองแล้วทำโมดูโลเลขคณิต $คิว$ (การบวกและการคูณ) มีประสิทธิภาพและตรงไปตรงมามาก?

เนื่องจากโปรเซสเซอร์มีการบวกและการคูณที่มีประสิทธิภาพอยู่แล้วในช่วงขนาดใหญ่ปานกลาง (32 หรือ 64 บิต) และการทำงานของโมดูโลนั้นมีประสิทธิภาพมาก (เพียงแค่ละทิ้งบิตด้านบน $คิว$ง่ายๆ และ ดำเนินการด้วยค่าคงที่) และเนื่องจากสำหรับการดำเนินการหลายอย่าง (รวมถึงการบวกและการคูณ) บิตลำดับที่สูงกว่าจะไม่ส่งผลกระทบต่อบิตลำดับที่ต่ำกว่า บางครั้งเราไม่จำเป็นต้องทำเช่นนั้นด้วยซ้ำ เราสามารถเพิกเฉยต่อพวกมันได้...

โพสต์คำตอบ

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