(ข้ามรายการใน math stackexchange ไม่ได้รับการตอบกลับ) สำหรับบริบท นี่เป็นคำถามการบ้านจากงานที่ส่งไปแล้ว ฉันกำลังมองหาความเข้าใจที่ดีขึ้นเกี่ยวกับแนวคิดที่เกี่ยวข้อง ส่วนใหญ่เป็นทฤษฎีความซับซ้อน เนื่องจากฉันไม่เคยเห็นมาก่อนนอกชั้นเรียนนี้ (และความรู้เดิมถูกสันนิษฐาน)
ฉันถูกขอให้ประเมินความซับซ้อนของการถอดรหัส RSA โดยมีและไม่ใช้ CRT โดยไม่ใช้ความซับซ้อนเชิงซีมโทติค ใช้แทน $c_1$ เป็นค่าคงที่สำหรับการคูณแบบแยกส่วน $c_2$ สำหรับการยกกำลังแบบโมดูลาร์ และ $c_3$ เพื่อหาผลคูณผกผัน
ความพยายามของฉัน: ให้ $s_1$ เป็นความยาวของ $p$, $s_2$ เป็นความยาวของ $คิว$, $s$ ความยาวของ $n$, และ $x$ ความยาวของ $d$. พิจารณาความซับซ้อนต่อไปนี้:
| การคำนวณ | ความซับซ้อน |
|---|---|
| $m_1=c^d\mod p$ | $c_2s_1^2x$ |
| $m_2=c^d\mod q$ | $c_2s_2^2x$ |
| $q^{-1}\mod p$ | $c_3s_1$ |
| $p^{-1}\mod q$ | $c_3s_2$ |
ดังนั้นความซับซ้อนของการใช้ CRT ในการคำนวณ $m=m_1(q^{-1}\mod p)q+m_2(p^{-1}\mod q)p\mod n$ เป็น $c_1^2c_2c_3s_1^3x+c_1^2c_2c_3s_2^3x=c_1^2c_2c_3x(s_1^3+s_2^3)$.
ในขณะเดียวกันความซับซ้อนในการคำนวณ $m=c^d\mod n$ เป็น $c_2s^2x$ดังนั้นความแตกต่างคือ $c_2x(s^2-c_1^2c_3(s_1^3+s_2^3))$.
ฉันเชื่อว่าสิ่งนี้ผิดเพราะฉันไม่คิดว่ามันจริงโดยทั่วไป $s^2\geq s_1^3+s_2^3$ (CRT ควรทำให้การถอดรหัสเร็วขึ้น) และฉันไม่รู้ว่าเราสามารถตั้งสมมติฐานเกี่ยวกับค่าคงที่ได้หรือไม่
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
