Thuật toán RHO

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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[sửa | sửa mã nguồn]

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ố xy đồ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) \le n từ đó p là ước số của \left|x-y\right|n.

Thuật toán[sửa | sửa mã nguồ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 1n) của n, hoặc không thực hiện được.

  1. x ← 2, y ← 2; d ← 1
  2. While d = 1:
    1. xf(x)
    2. yf(f(y))
    3. d ← GCD(|xy|, 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[sửa | sửa mã nguồ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 nsố 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[sửa | sửa mã nguồn]

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

Ví dụ phân tích[sửa | sửa mã nguồn]

Cho n = 8051 và f(x) = x2 + 1 mod 8051.

i xi yi GCD(|xiyi|, 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[sửa | sửa mã nguồn]

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

Tham khảo[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]