เครื่องคำนวณการแยกตัวประกอบแฟร์มา

เกี่ยวกับเครื่องคำนวณนี้

วิธีแยกตัวประกอบของแฟร์มาอาศัยข้อเท็จจริงว่าจำนวนเต็มคี่ N ใด ๆ เขียนเป็นผลต่างของกำลังสองสองจำนวนได้ N = a² − b² = (a−b)(a+b) อัลกอริทึมเริ่มที่ a = ⌈√N⌉ แล้วเพิ่ม a ทีละ 1 ในแต่ละขั้น พร้อมตรวจสอบว่า a² − N เป็นกำลังสองสมบูรณ์ (b²) หรือไม่ ทันทีที่เป็น N ก็แยกตัวประกอบได้เป็น (a−b)(a+b) เครื่องคำนวณนี้ทำงานวนซ้ำดังกล่าวและแสดงทุกขั้นที่ใช้หาตัวประกอบ

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