Thuật toán RHO

Thuật toán rho dựa trên cơ sở en: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 1.177√p số ngẫu nhiên. Nếu p là nhân tử của n, thì 1 < gcd (|x-y|,n) ≤ n từ đó p là ước số của |x-y| và 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 ← 2; 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.

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 gcd(a,n) > 1, thì cũng có gcd(ab,n) > 1 với mọi số nguyên dương b. Vì vậy, thay vì tính gcd( | x − y | ,n) tại mỗi bước, đi tính z là tích của 100 số | x − y | theo modulo n, và sau đó tính ước chung lớn nhất một lần gcd(z,n). Kết quả là 100 lần tính gcd được thay thế bởi 99 phép nhân modulo n và một phép tính gcd. 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 n là số chính phương. Nhưng nếu như vậy thì quay lại gcd, mà gcd(z,n) = 1, và sử dụng thuật toán Rho chính quy để tiếp tục.

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à:

f(x)=x²+c mod n,c ≠ 0,-2.

Đ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 F8 mất tổng cộng 2 giờ trên UNIVAC 1100/42.

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.

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^1/4 polylog(n)) bước.