ขั้นตอนวิธีพีลบหนึ่งของพอลลาร์ด

ขั้นตอนวิธีพีลบหนึ่งของพอลลาร์ด (อังกฤษ: Pollard's p - 1 algorithm) เป็นขั้นตอนวิธีในการหาตัวประกอบของจำนวนเต็มโดยใช้แนวคิดทางทฤษฎีจำนวนเป็นพื้นฐาน ขั้นตอนวิธีดังกล่าว จอห์น พอลลาร์ด (John Pollard) นำเสนอขึ้นในปี 1974

แนวคิดพื้นฐาน

ขั้นตอนวิธีพีลบหนึ่งของพอลลาร์ดมีพื้นฐานอยู่บนทฤษฎีบทเล็กของแฟร์มาต์ สำหรับจำนวนเต็ม a ซึ่งเป็นจำนวนเฉพาะสัมพัทธ์กับ p และสำหรับจำนวนเต็มบวก K แล้ว

${\displaystyle a^{K(p-1)}\equiv 1{\pmod {p}}}$

ถ้า x เป็นสมภาคกับ 1 มอดุโลด้วยตัวประกอบหนึ่งของ n เมื่อ n คือจำนวนเต็มที่ต้องการหาตัวประกอบ แล้วตัวประกอบนั้น ๆ ย่อมต้องหารตัวหารร่วมมากของ x - 1 และ n ได้ลงตัว ในการเลือกเต็มบวก K นั้นเพื่อนำไปหาร p - 1 นั้น มันจะให้ K เกิดผลคูณของเลขยกกำลังของจำนวนเฉพาะหลาย ๆ ตัว โดยมากแล้วมักจะเลือกจำนวนเฉพาะที่จะมาใช้เป็นตัวประกอบนั้นไม่ให้มีค่าเกินค่า ๆ หนึ่ง (ในที่นี้จะขอเรียกว่า B) เริ่มจากการสุ่มตัวเลข x มาหนึ่งตัว แล้วแทนค่าของ x ด้วย ${\displaystyle x^{w}\mod n}$ เมื่อ w แทนจำนวนเฉพาะที่ใช้เป็นเลขยกกำลัง ซึ่งขั้นตอนวิธีจะหาตัวประกอบของจำนวนเต็ม n ได้ก็ต่อเมื่อตัวหารร่วมมากของ x - 1 และ n ไม่เท่ากับ 1

ขั้นตอนวิธี และอัตราการเติบโต

ข้อมูลขาเข้า: จำนวนประกอบ n

ข้อมูลขาออก: ตัวประกอบของ n หรือข้อผิดพลาด (ในกรณีที่หาตัวประกอบไม่พบ)

1. เลือกขอบเขตบน B ของจำนวนเฉพาะที่จะนำมาใช้เป็นตัวประกอบของจำนวนเต็ม' K
2. ${\displaystyle M\gets \prod _{{\text{primes}}~q\leq B}q^{\lfloor \log _{q}{B}\rfloor }}$
3. สุ่มเลือก a ซึ่งเป็นจำนวนเฉพาะสัมพัทธ์กับ p (ข้อสังเกต: อย่างไรก็ตาม สามารถกำหนดค่าของ a ได้เองเลย เนื่องจากการสุ่มเลือกในขั้นตอนนี้ยังไม่จำเป็นเท่าไรนัก)
4. ${\displaystyle g\gets \gcd(a^{M}-1,n)}$ (โดยระหว่างการคำนวณ ${\displaystyle a^{M}}$ ให้ทำการมอดุโลด้วย n ควบคู่ไปด้วย)
5. ถ้า 1 < g < n นั่นคือพบตัวประกอบแล้ว ให้คืนค่า g
6. ถ้า g = 1 หรือ g = n ให้กลับไปเลือกค่า B ใหม่ที่มากกว่าเดิม แล้วย้อนกลับไปทำขั้นตอนที่ 2 อีกครั้ง หรือแสดงข้อผิดพลาดว่าหาไม่พบ

อัตราการเติบโตของขั้นตอนวิธีนี้คือ O(B × log B × log²n) โดยยิ่ง B มีค่ามาก ยิ่งทำให้ทำงานช้า แต่ทำให้โอกาสที่จะหาตัวประกอบพบนั้นเพิ่มมากขึ้น

ตัวอย่างการหาตัวประกอบ

ต้องการหาตัวประกอบของ n = 2987 โดยให้ a = 2 และ M = 7! (ในที่นี้จะขอเลือก M = 7 เพื่อความสะดวกในการแสดงตัวอย่างการคำนวณ) ด้วยขั้นตอนวิธีพีลบหนึ่งของพอลลาร์ด จึงต้องคำนวณหา ${\displaystyle 2^{7!}{\pmod {2987}}}$ ซึ่งคำนวณได้จาก

${\displaystyle (((((2^{2})^{3})^{4})^{5})^{6})^{7}{\pmod {2987}}}$

ซึ่งจะได้ลำดับของการคำนวณ ดังนี้

${\displaystyle 2^{2}\equiv 4{\pmod {2987}}}$

${\displaystyle 4^{3}\equiv 64{\pmod {2987}}}$

${\displaystyle 64^{4}\equiv 2224{\pmod {2987}}}$

${\displaystyle 2224^{5}\equiv 1039{\pmod {2987}}}$

${\displaystyle 1039^{6}\equiv 2227{\pmod {2987}}}$

${\displaystyle 2227^{7}\equiv 755{\pmod {2987}}}$

จากนั้น นำค่า 755 ที่ได้ไปลบออกหนึ่ง แล้วคำนวณหาตัวหารร่วมมากระหว่าง 755 -1 กับ n จะได้ว่า

${\displaystyle \gcd(755-1,n)=\gcd(754,2987)=29}$

นั่นคือ 29 เป็นตัวประกอบหนึ่งของ 2987 นั่นเอง

อ้างอิง

• Burton, David M. (2007), "Section 16.2: Primality Testing and Factorization", Elementary Number Theory (Sixth ed.), The McGraw-Hill Companies, NY: McGraw-Hill, pp. 356–357, ISBN 0071244255
• Pollard, J. M. (1974), "Theorems of Factorization and Primality Testing", Proceedings of the Cambridge Philosophical Society, 76 (3): 521–528, doi:10.1017/S0305004100049252

แหล่งข้อมูลอื่น

• เอริก ดับเบิลยู. ไวส์สไตน์, "Pollard p-1 Factorization Method" จากแมทเวิลด์.