งานเท่าไหร่ที่จะหา $n$ ดังกล่าว?

อนุญาต $W$ สุ่ม $200$ หมายเลขบิต ต้องใช้ความพยายามมากแค่ไหนในการหาเซมิไพรม์ $n=p_1\cdot p_2$ ดังนั้น $p_1,p_2 > 2^{50} $ และ $|W-n|<2^{12}$?

โดยทั่วไปให้ $W_b$ เป็นจำนวนเต็มสุ่มด้วย $ข$ บิต ต้องใช้ความพยายามมากแค่ไหนในการหาเซมิไพรม์ $n=p_1\cdot p_2$ ดังนั้น $p_1,p_2 > \sqrt[4]{W_b} $ และ $|W_b-n|<\sqrt[8]{W_b}$?

วิธีที่ดีที่สุดในการค้นหาตัวเลขที่ฉันรู้คืออัลกอริทึม 3 จากกระดาษของ Marc Joye RSA Moduli พร้อมส่วนที่กำหนดไว้ล่วงหน้า: เทคนิคและการใช้งาน. ในกรณีนี้การ $n=200$, $n_0=150$ และ $\kappa'=188$. ข้อกำหนดของปัญหาเริ่มต้นนั้นรุนแรงและเป็นไปได้มากที่จะมีค่า 200 บิตเป็น $W$ ซึ่งไม่มีช่วงกึ่งไพรม์ที่เหมาะสมในช่วงเวลานั้นการสืบสวนของ Joye ตรวจสอบความซับซ้อนของวิธีการในลักษณะการทดลองเท่านั้น ฉันจะอ่านและพยายามคิดแบบฮิวริสติก

เป็นเรื่องง่ายที่จะอธิบายและวิเคราะห์วิธีการ "ชาวบ้าน" ในการเลือก 50 บิตด้วยวิธีฮิวริสติก $p$การตั้งค่า $q_0=\lceil W/p\rceil$ และการทดสอบ $q_0$ สำหรับความเป็นอันดับหนึ่ง ควรใช้เวลาประมาณ 105 ตัวเลือกที่แตกต่างกัน $p$ เพื่อหานายก $คิว$ 150 บิต สำหรับคู่นี้ 150 บิตสูงสุดจะตรงกัน $W$ และด้วยความน่าจะเป็น $2^{-38}$ 188 บิตสูงสุดจะตรงกัน สิ่งนี้ให้งบประมาณการทำงานโดยรวม 44-45 บิตสำหรับการทดสอบเบื้องต้น วิธีการของ Joye จะดีขึ้นอย่างแน่นอน แต่การวิเคราะห์จะยาวขึ้น

สำหรับคำถามทั่วไปกับ $q\ประมาณ\root 4\of n$ และช่วงระยะ $\root 8\of n$, เราจะคาดหวังประมาณ $\frac14\root 8\of n\log n$ การทดสอบเบื้องต้นของตัวเลขรอบตัว $\root 4\of n$ ขนาดสำหรับวิธีการชาวบ้าน แต่อีกครั้ง Joye ควรปรับปรุงในเรื่องนี้

หากคุณใช้ฟังก์ชันแฟคตอริ่งที่มีอยู่ จะสามารถแก้ไขได้ภายในไม่กี่นาที สำหรับตัวเลขสุ่ม 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