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 $1.177\backslash sqrt\{p\}$ số ngẫu nhiên. Nếu p là nhân tử của n, thì từ đó p là ước số của $\backslash left|x-y\backslash right|$ 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.

x ← 2, y ← 5; d ← 1

While d = 1:

x ← f(x)

y ← f(f(y))

d ← GCD(|x − y|, n)

If d = n, return không thực hiện được.

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 $\backslash gcd\; (a,n)\; >1$, thì cũng có $\backslash gcd\; (ab,n)>1$ với mọi số nguyên dương $b$. Vì vậy, thay vì tính $\backslash 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 $\backslash 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à $\backslash gcd(z,n)=1$, 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à:

:$f(x)=x^2+c\backslash hbox\{\; mod\; \}n,\backslash ,c\backslash neq0,-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 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^1/4 polylog(n)) bước.