หากคุณใช้ฟังก์ชันแฟคตอริ่งที่มีอยู่ จะสามารถแก้ไขได้ภายในไม่กี่นาที
สำหรับตัวเลขสุ่ม 200 บิต ฟังก์ชันการแยกตัวประกอบจาก Pari/GP เป็นต้น
อัลกอริทึมด้านล่างไม่ใช่แค่การแยกตัวประกอบของตัวเลขที่ต่อเนื่องกันเท่านั้น ดูด้านล่าง
นี่คืออัลกอริทึมทั่วไปที่ได้รับการแปลงเป็นการทำงาน
โปรแกรม:
สร้าง W ซึ่งเป็นตัวเลขสุ่ม 200 บิต
ตะแกรงจำกัด = 250
ไพรม์ลิมิต = 2000000
คำนวณล่วงหน้า pr = ผลคูณของไพรม์ลิมิตไพรม์ตัวแรก
สำหรับ n1 = W+1 ถึง W+ตะแกรงจำกัด
ถ้า n1 อยู่ในรูป 6k+1 หรือ 6k+5
ถ้า gcd(n1,pr) เป็น 1
ฉ = ปัจจัย (n1)
ถ้าจำนวนตัวประกอบของ n1 เป็น 2 และทั้งคู่ >2^50
โซลูชันการพิมพ์ f
ห่วง
เส้น:
ถ้า gcd(n1,pr) เป็น 1
เป็นวิธีที่รวดเร็วในการข้ามจำนวนที่มีตัวประกอบเฉพาะต่ำกว่า 2 ล้านเฉพาะ
ขั้นตอน precompute pr ได้รับการปรับให้เหมาะสมใน Pari/GP และใช้เวลาเพียง 7.785 วินาทีสำหรับฮาร์ดแวร์ที่ช้า
สำหรับกรณีที่เลวร้ายที่สุด 200 บิต ฟังก์ชันตัวประกอบใน Pari/GP ใช้วิธี MPQS และใช้เวลาน้อยกว่า 30 วินาทีในฮาร์ดแวร์เก่า
นี่คือหมายเลขสุ่ม 200 บิต W:
1567470448908230034126591070540826459978233372650796513704199
โปรแกรมจะแยกเฉพาะตัวเลข W+10 หนึ่งตัวและค้นหาคำตอบ
p1 = 5346955435967300929
p2 = 293151956787285973328498761492202409914321
p1 คือ 63 บิต, p2 คือ 138 บิต, n = p1*p2
|W-n| = 10, |W-n|< 2^12