Score:6

เหตุใดเราจึงใช้ฟังก์ชัน Zeta เพื่อค้นหาปัจจัยสำคัญใน RSA ไม่ได้

ธง cn

บางทีฉันอาจเข้าใจผิด แต่ถ้าฟังก์ชัน Zeta มีประสิทธิภาพในการคำนวณและย้อนกลับ และถ้าสมมติฐานของ Riemann เป็นจริง (ซึ่งดูเหมือนจะเป็นเช่นนั้น) เราจะใช้ฟังก์ชัน Zeta เพื่อค้นหาปัจจัยเฉพาะของจำนวนมากอย่างมีประสิทธิภาพและหาค่าส่วนตัวไม่ได้หรือ คีย์ของคีย์ RSA สาธารณะ?

kelalaka avatar
in flag
ยินดีต้อนรับสู่ Cryptography.se คุณหมายถึงอะไรโดย _ประสิทธิภาพในการคำนวณและย้อนกลับ_?
stimulate avatar
cn flag
@kelalaka มีประสิทธิภาพในการคำนวณ: โดยพื้นฐานแล้วสามารถคำนวณได้ในเวลาน้อยกว่าเลขชี้กำลังตามลำดับเวลาที่เรากำลังค้นหา ย้อนกลับ: มีประสิทธิภาพในการค้นหาอินพุตของซีตาสำหรับจำนวนเฉพาะที่กำหนด
Score:11
ธง ru

ประการแรกฉันไม่คิดว่า $\ซีต้า(s)$ ที่มีประสิทธิภาพในการคำนวณ ความสนใจของเราในการคำนวณ $\ซีต้า(s)$ สำหรับวัตถุประสงค์ทางทฤษฎีจำนวนเฉพาะมักจะมุ่งเน้นไปที่เส้นวิกฤต $\mathrm{Re}s=1/2$ และ สูตรรีมันน์-ซีเกล ต้องใช้ $O(t^{1/2})$ ข้อกำหนดในการคำนวณ $\zeta(1/2+it)$. มีการเร่งความเร็วสำหรับการคำนวณค่าทวีคูณ แต่ไม่มากนัก

ในทำนองเดียวกัน ฉันไม่แน่ใจว่าคุณหมายถึงอะไรโดยย้อนกลับ ฟังก์ชันไม่ใช่ bijective (เรารู้ว่าหลายแห่งที่เป็นศูนย์ เป็นต้น)

ที่กล่าวว่า มีแนวคิดบางอย่างเกี่ยวกับการใช้ทฤษฎีจำนวนวิเคราะห์สำหรับวิธีการแยกตัวประกอบ วิธีการแยกตัวประกอบของกลุ่มคลาสของแชงค์สสามารถเร่งความเร็วได้หากสามารถประมาณค่าได้ $L(1,\chi_N)$ (ที่นี่ $L$- ฟังก์ชั่นสำหรับฟิลด์ตัวเลข $\mathbb Q(\sqrt N)$ และมีความเกี่ยวข้องอย่างใกล้ชิดกับ $\ซีต้า(s)$. ด้วยสมมติฐานทั่วไปของรีมันน์ แชงค์สสามารถลดเวลาการทำงานของอัลกอริธึมของเขาในการแยกตัวประกอบได้ $N$ จาก $O(N^{1/4+\epsilon})$ ถึง $O(N^{1/5+\epsilon})$. ความซับซ้อนดังกล่าวไม่น่าที่จะแยกจำนวนที่มากกว่าสองสามร้อยบิตและไม่สามารถแข่งขันได้ ตะแกรงฟิลด์ตัวเลขทั่วไป.

ได้มีการนำแนวคิดไปใช้ $\ซีต้า(s)$ เอง (ดูกระดาษล่าสุด "การแยกตัวประกอบพร้อมคำแนะนำ" โดย Sica เป็นต้น) แต่สิ่งเหล่านี้พยายามที่จะเข้าใกล้ความซับซ้อนของวิธีการของ Shanks ในช่วงปี 1970 (กระดาษของ Sica มีความซับซ้อน $O(N^{1/3+\epsilon})$.)

Score:4
ธง us

เราไม่สามารถใช้ฟังก์ชัน Zeta เพื่อค้นหาปัจจัยเฉพาะของตัวเลขจำนวนมากและค้นหาคีย์ส่วนตัวของคีย์ RSA สาธารณะได้อย่างมีประสิทธิภาพ

ในระยะสั้น: The $\ซีต้า$ การทำงาน ไม่ให้เข้าถึงหมายเลขเฉพาะแต่ละตัว (ผมไม่รู้ว่ามีสูตรไหนทำ) ดังนั้นแม้ว่าเราจะมีวิธีคำนวณที่เร็วมาก แต่ก็ไม่สามารถนำมาใช้ได้ หา จำนวนเฉพาะ.


  • สิ่งที่ $\ซีต้า$ ฟังก์ชันให้การเข้าถึง ตัวอย่างเช่น ตัวเลข ของจำนวนเฉพาะระหว่าง $1$ และ $x$เช่น ฟังก์ชันการนับจำนวนเฉพาะ $\pi(x)$.

    มีความสัมพันธ์ระหว่างฟังก์ชันการนับจำนวนเฉพาะ $\pi(x)$และเลขศูนย์ทั้งหมด $\rho$ ของรีมันน์ $\ซีต้า$ การทำงาน:

    $$\psi _{0}(x)=x-\sum _{\rho }{\frac {x^{\rho }}{\rho }}-\ln 2\pi -{\frac 12}\ ln(1-x^{{-2}}).$$

    นี่นึกถึง $\psi_0(x)$ เป็นสิ่งที่ใกล้ตัวมาก $\pi(x)$ ในความคิด แต่เป็นการนับจำนวนเฉพาะที่มีน้ำหนักอื่นมากกว่า $1$ สำหรับแต่ละจำนวนเฉพาะ แทนที่จะเป็นน้ำหนัก $\log พี$. นี่เป็นการละเว้นรายละเอียด แต่ให้แนวคิด ดู ที่นี่ เพื่อความแม่นยำยิ่งขึ้น

  • ผลิตภัณฑ์ออยเลอร์สำหรับ $\ซีต้า$ ฟังก์ชันเกี่ยวข้องกับจำนวนเฉพาะทั้งหมด แต่ไม่ได้ให้วิธีที่มีประสิทธิภาพในการสร้าง / ค้นหาจำนวนเฉพาะ:

    $$\zeta(s) = \sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ ไพรม์}}}{ \frac {1}{1-p^{-s}}}$$

โพสต์คำตอบ

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