Pollard's p - 1 - คุณตั้งค่าขอบเขตอย่างไร & คุณจะตั้งค่าเลขฐานได้อย่างไร

ในอัลกอริทึม p-1 ของ Pollard สำหรับการแยกตัวประกอบ N คุณพยายามหา L โดยที่ p - 1 หาร L จากนั้นคุณตรวจสอบ $gcd(pow(a,L,N)- 1, N)$. ถ้า 1 < gcd < N แสดงว่าคุณพบปัจจัยอย่างใดอย่างหนึ่งแล้ว

ฉันได้เห็น 2 วิธีในการทำเช่นนี้

1. สำหรับ n จาก 1 ถึง Bound ลอง $L = n!$ (เช่น แฟคทอเรียล(n)) & ลองใช้ $gcd(pow(a,L,N)- 1, N)$ สำหรับแต่ละคน
2. สำหรับ n จาก 1 ถึง Bound ลอง $L = LCM(ช่วง(1,n))$ & ลอง $gcd(pow(a,L,N)- 1, N)$ สำหรับแต่ละคน

ในทั้งสองวิธี เมื่อคุณไปถึงขอบเขตไม่สำเร็จโดยไม่พบปัจจัย คุณจะทำซ้ำลูปใหม่ด้วย $a$

ฉันมีคำถามสองสามข้อ

1. คุณจะเลือกขอบเขตสำหรับแต่ละวิธีจาก 2 วิธีได้อย่างไร คุณกำลังพยายามตรวจสอบว่าปัจจัยคือ Bound-Powersmooth หรือไม่ แต่คุณมาถึงสิ่งที่ต้องการตรวจสอบ Bound ได้อย่างไร เช่น คุณคาดหวังความราบรื่นของพลังแบบใด
2. ในทั้งสองวิธี วิธีการเลือก $a$เหรอ?
3. ในทั้งสองวิธีมีกี่วิธี $a$' คุณลองก่อนที่จะยอมแพ้ (เพราะ p - 1 คงไม่มีปัจจัยเล็กๆ น้อยๆ)?

p-1 ของพอลลาร์ดจะมีประโยชน์ก็ต่อเมื่อ p-1 เป็นจำนวนเฉพาะของไพรม์ p เท่านั้น หากคุณมีจำนวนเต็มสุ่มที่คุณต้องการแยกตัวประกอบ คุณจะใช้ ECM และ GNFS ซึ่งหมายความว่า หากคุณกำลังลองใช้ p-1 คุณก็มีเหตุผลที่จะสงสัยว่า p-1 นั้นราบรื่นพอสมควร และคุณก็น่าจะรู้แล้วว่ามันจะราบรื่นได้อย่างไร (ขอบเขตความเรียบ L) ไม่ว่าในกรณีใด ยิ่งคุณพยายามมากเท่าไหร่ คุณก็ยิ่งมีโอกาสที่จะหักได้ ดังนั้นคุณควรกำหนดขอบเขตให้ใหญ่ที่สุดเท่าที่คุณจะทนได้ แต่ถ้าคุณมีเหตุผลที่จะสงสัยว่า p-1 จะราบรื่น

ฉันเชื่อว่าการเลือก $a$ ไม่สำคัญมากนักและเปลี่ยนแปลง $a$ ไม่มีประโยชน์เลยจนกว่าคุณจะได้เรื่องไร้สาระ $gcd$. แนวคิดก็คือว่าสำหรับใหม่ $a$ คุณต้องคูณด้วยสิ่งเหล่านั้นทั้งหมด $1,2,3,...$ อีกครั้งในขณะที่คุณได้ทำงานนี้ไปแล้วก่อนหน้านี้ $a$. คุณอาจได้รับใหม่ $a$ เช่นปัจจัยขนาดใหญ่บางอย่าง $d$ ของ $p-1$ ถูกลบออกไปแล้ว และจากนั้นคุณต้องมีขอบเขตที่เล็กลง $L$ ในการทำงาน แต่โอกาสที่จะเป็นเช่นนั้น $1/ด$ และคุณค่อนข้างจะยกระดับต้นฉบับของคุณต่อไป $a$ สู่อำนาจต่อไปและก้าวสู่อำนาจ $d$ อย่างเป็นธรรมชาติ

ปัญหาเดียวที่สามารถเกิดขึ้นได้ - คือคุณจะมาถึง 1 mod $p$ และ 1 รุ่น $คิว$ พร้อมกัน (เช่น รับ $a^L\equiv 1 \mod{n}$) ซึ่งไม่มีการรั่วไหลของปัจจัย จากนั้นคุณลองอีกครั้ง $a$แต่อย่างน้อยคุณก็ได้เรียนรู้ว่าพอลลาร์ด $p-1$ น่าจะไปได้ดีกับเลขนี้