Thuật toán RHO

Thuật toán RHO (còn gọi là thuật toán Pollard's rho) là một thuật toán phân tích số nguyên thành thừa số. được phát minh bởi John Pollard vào năm 1975. Nó tỏ ra hiệu quả khi phân tích các số với nhân tử nhỏ.

== Ý tưởng chính ==
Thuật toán rho dựa trên cơ sở Floyd's cycle-finding algorithm và trên sự đánh giá (còn gọi là vấn đề ngày sinh nhật) rằng hai số "x" và "y" đồng dư modulo "p" với xác suất 0.5 sau khi chọn formula_1 số ngẫu nhiên. Nếu "p" là nhân tử của "n", thì formula_2 từ đó "p" là ước số của formula_3 và "n".

== Thuật toán ==
Inputs: "n", số nguyên cần phân tích; và "f"("x"), hàm tạo số giả ngẫu nhiên modulo "n"

Output: một nhân tử không tầm thường (khác "1" và "n") của "n", hoặc "không thực hiện được".
1. "x" ← 2, "y" ← 5; "d" ← 1
2. While "d" = 1:
1. "x" ← "f"("x")
2. "y" ← "f"("f"("y"))
3. "d" ← GCD(|"x" − "y"|, "n")
3. If "d" = "n", return "không thực hiện được".
4. Else, return "d".

Chú ý rằng thuật toán có thể không tìm thấy nhân tử và trả về kết quả "không thực hiện được" với một hợp số "n". Trong trường hợp này sử dụng hàm "f"("x") khác và thử lại.
Thuật toán cũng không làm việc khi "n" là số nguyên tố, trong trường hợp này "d" sẽ luôn là 1.

== Tăng tốc thuật toán ==
Năm 1980, Richard Brent công bố một biến thể nhanh hơn của thuật toán rho. Ông ấy sử dụng ý tưởng của Pollard nhưng thay đổi method of cycle detection, thay Floyd's cycle-finding algorithm bằng Brent's cycle finding method.

Những cải tiến xa hơn nữa đã được tạo ra bởi Pollard và Brent.
Họ nhận thấy rằng nếu formula_4, thì cũng có formula_5 với mọi số nguyên dương formula_6. Vì vậy, thay vì tính formula_7 tại mỗi bước, đi tính formula_8 là tích của formula_9 số formula_10 theo modulo n, và sau đó tính ước chung lớn nhất một lần formula_11. Kết quả là 100 lần tính formula_12 được thay thế bởi formula_13 phép nhân modulo formula_14 và một phép tính formula_12. Thỉnh thoảng thuật toán bị hỏng do tạo ra các nhân tử lặp lại, một ví dụ đơn giản là khi formula_14 là số chính phương. Nhưng nếu như vậy thì quay lại gcd, mà formula_17, và sử dụng thuật toán Rho chính quy để tiếp tục.

== Trong thực hành ==
Thuật toán tỏ ra khá nhanh với những số có một vài nhân tử nhỏ. Ví dụ, trên máy 3 GHz, thuật toán rho nguyên thủy tìm thấy nhân tử 274177 số Fermat thứ sáu là (18446744073709551617) trong 26 mili-giây; biến thể của Richard Brent cũng tìm thấy nhân tử đó trong 5 mili-giây. Tuy nhiên đối với số nửa nguyên tố cùng cỡ (10023859281455311421), cùng trạm làm việc, sử dụng thuật toán rho nguyên mẩu mất 109 mili-giây để tìm nhân tử; biến thể của Richard Brent chỉ mất 31 mili-giây.

Đối với hàm "f", chúng ta chọn đa thức với hệ số nguyên. một trong những dạng chung nhất đó là:

Điều đáng chú ý nhất của thuật toán rho là thành công trong việc phân tích số fermat thứ tám bởi Pollard và Brent. Họ đã dùng biến thể của Brent, để tìm nhân tử trước đó chưa biết. Để hoàn thành việc phân tích "F" mất tổng cộng 2 giờ trên UNIVAC 1100/42.

== Ví dụ phân tích ==
Cho "n" = 8051 và "f"("x") = "x" + 1 mod 8051.

97 là một nhân tử không tầm thường của 8051. Nhân tử còn lại là thương của phép chia n cho 97.

== Độ phức tạp ==
Thuật toán cung cấp sự cân bằng giữa thời gian thực hiện và xác suất tìm thấy nhân tử.
Nếu n là tích của hai số nguyên tố phân biệt cùng số chữ số, Thuật toán chạy với O(n "polylog"(n)) bước.

== Tham khảo ==
- J.M. Pollard. "A Monte Carlo method for factorization", BIT Numerical Mathematics 15(3), 1975, pp. 331–334.
- Richard P. Brent. "An Improved Monte Carlo Factorization Algorithm", BIT 20, 1980, pp. 176–184, http://wwwmaths.anu.edu.au/~brent/pd/rpb051i.pdf
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. "Introduction to Algorithms", Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.9: Integer factorization, pp. 896–901 (this section discusses only Pollard's rho algorithm).

== Liên kết ngoài ==
- Minh họa trên Java