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

ขั้นตอนวิธีโรห์ของพอลลาร์ด  เป็นขั้นตอนวิธีแบบสุ่มที่ใช้หาตัวประกอบของจำนวนประกอบที่มีค่ามาก โดยอาศัยคุณสมบัติของการหาร เพื่อให้หาตัวประกอบของเลขจำนวนนั้น ๆ ได้เร็ว ขั้นตอนวิธีนี้ จอห์น พอลลาร์ด  นำเสนอขึ้นในปี 1975 และต่อมา ริชาร์ด เบรนท์  ปรับปรุงในปี 1980
แนวความคิดหลัก.
ขั้นตอนวิธีโรห์ของพอลลาร์ดมีพื้นฐานมาจาก ขั้นตอนวิธีการตรวจสอบการเกิดวงวนของฟลอยด์  และ จากการสังเกตถึงคุณสมบัติของตัวเลขที่จะมีคุณสมบัติหนึ่ง ๆ เหมือนกัน ซึ่งคล้ายกับในปัญหาวันเกิด  นั่นคือ หากต้องการหาตัวเลข 2 ตัว "x" และ "y" ที่มีคุณสมบัติหารด้วยตัวเลข "p" แล้วมีเศษเหลือเท่ากัน หรือ "x" สมภาคกับ "y" มอดุโล "p" ("x" congruent "y" modulo "p") จะมีความน่าจะเป็นเท่ากับ 0.5 หลังจากสุ่มตัวเลขมาแล้ว <math>1.177\sqrt{p} </math> ตัว หากให้ "p" เป็น ตัวประกอบหนึ่งของ "n" เมื่อ "n" คือตัวเลขที่ต้องการหาตัวประกอบ จะได้ว่า <math>p \le \gcd \left (x-y,n \right) \le n</math> เนื่องจาก "p" หาร <math>x-y</math> และ <math>n</math> ลงตัว
ขั้นตอนวิธีโรห์ จะใช้ "f" ฟังก์ชันมอดุโล "n" สำหรับการสร้างลำดับตัวเลขสุ่มเทียม  โดยลำดับทั้งสองจะมีความเร็วในการเลื่อนลำดับต่างกัน 2 เท่า กล่าวคือ ลำดับหนึ่งจะเลื่อนไป 2 ขั้น ในขณะที่อีกลำดับ จะเลื่อนไปเพียง 1 ขั้นเท่านั้น
หากให้ "x" และ "y" เป็นตัวแทนสำหรับตัวเลขในลำดับทั้ง 2 ในขณะหนึ่ง จะทำการหาค่า ห.ร.ม. (GCD) ของ <math>|x-y|</math> และ <math>n</math> โดยถ้าหาก ห.ร.ม. มีค่า
ขั้นตอนวิธี.
นำเข้า: "n", เป็นเลขจำนวนเต็มที่ต้องการหาตัวประกอบ; และ "f" ("x"), เป็นฟังก์ชันสุ่มเทียมมอดุโล "n"
ส่งออก: ตัวประกอบของ "n", หรือพบข้อผิดพลาด (หาไม่เจอ)
หมายเหตุ: ขั้นตอนวิธีนี้อาจจะไม่พบตัวประกอบ และแจ้งว่าพบข้อผิดพลาดถึงแม้ว่า "n" จะเป็นจำนวนประกอบ สำหรับกรณีนี้ให้เปลี่ยน "f" ("x") และลองทำอีกครั้ง
หมายเหตุ: ขั้นตอนวิธีนี้ไม่สามารถทำงานได้หาก "n" เป็นจำนวนเฉพาะ เนื่องจาก "d" จะเป็น 1 เสมอ
การปรับปรุง.
ในปี 1980 ริชาร์ด เบรนท์ ได้ตีพิมพ์ผลงานที่เร็วกว่า เขาได้ใช้แนวความคิดหลักเช่นเดียวกับ พอลลาร์ด แต่แตกต่างกันในเรื่องของขั้นตอนวิธีการตรวจสอบการเกิดวงวน โดยได้ใช้ วิธีการตรวจสอบการเกิดวงวนของเบรนท์ (Brent's cycle finding method) แทนขั้นตอนวิธีการตรวจสอบการเกิดวงวนของฟลอยด์
การเพิ่มประสิทธิภาพในครั้งต่อมาถูกกระทำโดย พอลลาร์ด และเบรนท์ ทั้ง 2 ได้พบว่า ถ้า <math>\gcd (a,n) >1</math> แล้ว <math>\gcd (ab,n) >1</math> สำหรับทุกๆจำนวนเต็มบวก "b" ใดๆ กล่าวโดยละเอียดคือ แทนที่จะคำนวณหา <math>\gcd (|x-y|,n) </math> ทุกๆขั้น, จะทำการกำหนดค่า "z" เป็นผลคูณของ พจน์ <math>|x-y|</math> จำนวน 100 พจน์ที่ติดกัน มอดุโล "n" และคำนวณหา <math>\gcd (z,n) </math> เพียงหนึ่งครั้ง โดยความเร็วที่เพิ่มขึ้นนั้นได้จากการเปลี่ยน การหา ห.ร.ม. จำนวน 100 ครั้ง เป็นการ คูณ มอดุโล "n" จำนวน 99 ครั้ง และ การหา ห.ร.ม 1 ครั้ง
แต่ในบางครั้ง วิธีนี้อาจจะทำให้ขั้นตอนวิธีเกิดข้อผิดพลาดโดยการใช้ตัวประกอบที่ซ้ำกัน ตัวอย่างเช่น เมื่อ "n" เป็นจำนวนเต็มกำลัง 2 แต่ก็สามารถจะแก้ไข้ได้โดยย้อนกลับไปที่จุดที่ <math>\gcd (z,n) =1</math> แล้วใช้ ขั้นตอนวิธีโรห์ แบบปกติจากจุดนั้น
การใช้งาน.
ขั้นตอนวิธีโรห์มักถูกนำไปใช้ในการหาตัวประกอบของจำนวนที่มีขนาดใหญ่ ที่ไม่สามารถหาได้อย่างรวดเร็วด้วยขั้นตอนวิธีแบบปกติ โดยเฉพาะจำนวนที่เกิดจากการนำจำนวนเฉพาะขนาดใหญ่สองตัวคูณกัน
ขั้นตอนวิธีโรห์จะใช้เวลาในการหาตัวประกอบได้อย่างรวดเร็วหากตัวประกอบนั้นมีค่าน้อย ตัวอย่างเช่น บนเครื่องที่มีความเร็ว 3 GHz ขั้นตอนวิธิโรห์ของพอลลาร์ดสามารถหาตัวประกอบ 274177 ของจำนวนแฟร์มาต์ลำดับที่ 6 (18446744073709551617) ในเวลา 26 มิลลิวินาที; ขั้นตอนวิธีโรห์ที่ถูกปรับปรุงโดยเบรนท์ สามารถหาตัวประกอบเดียวกันนี้ในเวลา 5 มิลลิวินาที แต่สำหรับจำนวนที่เกิดจากจำนวนเฉพาะสองตัวคูณกัน และที่มีความยาวเท่ากันกับจำนวนแฟร์มาต์ลำดับที่ 6 นั้น (10023859281455311421) การทำงานหาตัวประกอบบนเครื่องเดียวกัน ขั้นตอนวิธีโรห์ของพอลลาร์ดต้องใช้เวลาถึง 109 มิลลิวินาทีถึงจะพบตัวประกอบ ส่วนขั้นตอนวิธีโรห์ที่ถูกปรับปรุงใช้เวลา 31 มิลลิวินาที
สำหรับ "f" ฟังก์ชันตัวสุ่มเทียมมอดุโล "n" จะเลือกใช้ฟังก์ชัน พหุนาม พร้อมกับค่าคงที่จำนวนเต็ม "c" โดยรูปแบบที่นิยมใช้มากที่สุดคือ
 <math>f (x) = (x^2+c) \hbox{ mod }n,\,c\neq0,-2</math>
ขั้นตอนวิธีโรห์มีความโดดเด่นจากความสำเร็จในการหาตัวประกอบของจำนวนแฟร์มาต์ลำดับที่ 8 โดย พอลลาร์ด และ เบรนท์ ซึ่งใช้เวลาทั้งหมด 2 ชั่วโมงบนเครื่อง UNIVAC 1100/42
ตัวอย่างการหาตัวประกอบ.
ให้ "n" = 8051 และ "f" ("x") = ("x"2 + 1) mod 8051
97 เป็นตัวประกอบของ 8051 สำหรับการเปลี่ยนค่า c อาจจะให้คำตอบเป็นตัวประกอบอีกตัวคือ 83 แทนที่จะเป็น 97
อัตราการเติบโต.
ขั้นตอนวิธีแบบสุ่มนี้ต้องแลกเปลี่ยนระหว่างเวลาที่ใช้ในการค้นหา กับโอกาสที่จะค้นพบตัวประกอบ นั่นคือหากต้องการให้โอกาสที่จะค้นพบตัวประกอบนั้นมีค่าสูง ก็จะต้องใช้เวลามากขึ้น ถ้าหาก "n" เป็นผลคูณของจำนวนเฉพาะที่มีความยาวเท่ากัน แต่มีค่าแตกต่างกัน ระยะเวลาที่ใช้สำหรับขั้นตอนวิธีนี้ จะต้องสุ่มตัวเลขมา O (n1/4 "polylog" (n)) ครั้ง ถึงจะมีความน่าจะเป็นในการค้นพบตัวประกอบเท่ากับ 0.5 สำหรับพจน์ n1/4 นั้นก็มาจากที่ "n" เป็นผลคูณของจำนวนเฉพาะที่มีความยาวเท่ากัน ดังนั้น n1/2 ก็จะได้ค่าที่ใกล้เคียงกับจำนวนเฉพาะที่เป็นตัวประกอบของ "n" และจากที่ทราบว่า ความน่าจะเป็นในการพบตัวประกอบเท่ากับ 0.5 เมื่อสุ่มตัวเลขมาแล้ว <math>1.177\sqrt{p} </math> ตัว เมื่อ "p" คือตัวประกอบของ "n" ดังนั้นหากแทนค่า "p" ด้วย n1/2 ก็จะได้พจน์ n1/4 (หมายเหตุ: การวิเคราะห์นี้เป็นเพียงการประมาณโดยคร่าว ๆ สำหรับการวิเคราะห์อย่างละเอียด ยังรอให้พิสูจน์อยู่)
สรุป.
ขั้นตอนวิธีโรห์ของพอลลาร์ดช่วยให้สามารถแยกตัวประกอบของจำนวนใหญ่ ๆ ได้อย่างรวดเร็ว โดยอาศัยขั้นตอนวิธีแบบสุ่ม (ใช้ฟังก์ชันสร้างลำดับตัวเลขสุ่มเทียม) ซึ่งทำได้ดีกว่าขั้นตอนวิธีตามปกติที่จะใช้เวลานานกว่ามาก แต่ก็ต้องพึงระวังว่าคำตอบที่บอกว่าไม่พบตัวประกอบนั้นอาจจะผิด เพราะมีโอกาสที่หาแล้วไม่พบ เนื่องจากสุ่มตัวเลขไม่มากพอที่จะเจอตัวประกอบนั้น การนำขั้นตอนวิธีโรห์ไปใช้จึงต้องเลือกให้ดีว่า อยากจะให้ทำงานได้เร็วแค่ไหน อยากจะให้โอกาสผิดน้อยขนาดไหนถึงยอมรับได้ ซึ่งเป็นสองสิ่งที่ต้องแลกเปลี่ยนกัน โดยสรุป ขั้นตอนวิธีโรห์นี้สามารถนำไปใช้งานในการแยกตัวประกอบได้จริง และมีประสิทธิภาพที่น่าประทับใจอีกด้วย