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

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 $\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.

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{\hbox{ mod }}n,\,c\neq 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 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.

i	xi	yi	GCD(|xi − yi|, 8051)
1	5	26	1
2	26	7474	1
3	677	871	97

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.

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 Lưu trữ 2009-09-24 tại Wayback Machine
• 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 Lưu trữ 2009-03-27 tại Wayback Machine