หลักการอัลกอริทึม:
Pollard Rho เป็นอัลกอริทึมความน่าจะเป็นสำหรับการแยกตัวประกอบจำนวนเต็ม เหมาะสำหรับการหาตัวประกอบขนาดกลางของจำนวนประกอบ ชื่ออัลกอริทึมมาจากเส้นทางการทำงานที่คล้ายตัวอักษรกรีก ρ (rho)
กลยุทธ์การปรับปรุง:
- การปรับปรุงการลองหาร:ลองหารด้วยจำนวนเฉพาะเล็ก (2, 3, 5, 7, 11...) ก่อน เพื่อหาตัวประกอบเล็กได้รวดเร็ว
- Pollard Rho:สำหรับจำนวนประกอบที่ใหญ่กว่า ใช้ลำดับสุ่มเทียม x = (x² + c) mod n เพื่อหาตัวประกอบ
- อัลกอริทึมตรวจห่วง Floyd:ใช้ตัวชี้เร็ว-ช้าในการตรวจจับห่วงในลำดับ ปรับปรุงประสิทธิภาพพื้นที่
- การทดสอบจำนวนเฉพาะ Miller-Rabin:หลังจากพบตัวประกอบ ให้ตรวจสอบว่าเป็นจำนวนเฉพาะหรือไม่ เพื่อหลีกเลี่ยงการแยกต่อ
- การแยกแบบเรียกซ้ำ:แยกตัวประกอบที่พบแบบเรียกซ้ำ จนกว่าตัวประกอบทั้งหมดเป็นจำนวนเฉพาะ
ความซับซ้อนของเวลา:
- การลองหาร:O(√n) เหมาะสำหรับตัวเลขขนาดเล็กหรือการหาตัวประกอบเล็ก
- Pollard Rho:เวลาที่คาดหวัง O(n^(1/4)) มีประสิทธิภาพสูงสำหรับตัวเลขที่มีตัวประกอบขนาดกลาง
- Miller-Rabin:O(k log³n) โดย k คือจำนวนรอบการทดสอบ ใช้สำหรับการตรวจสอบจำนวนเฉพาะ