Nguyên tắc thuật toán:
Pollard Rho là một thuật toán xác suất để phân tích số nguyên, đặc biệt hiệu quả trong việc tìm các thừa số cỡ trung bình của các số tổng hợp. Tên của thuật toán xuất phát từ quỹ đạo của nó giống với chữ cái Hy Lạp ρ (rho).
Chiến lược tối ưu hóa:
- Tối ưu hóa phân chia thử nghiệm:Đầu tiên, sử dụng các số nguyên tố nhỏ (2, 3, 5, 7, 11...) để chia thử để tìm nhanh các thừa số nhỏ.
- Pollard Rho:Đối với các số tổng hợp lớn hơn, hãy sử dụng dãy giả ngẫu nhiên x = (x² + c) mod n để tìm các thừa số.
- Thuật toán phát hiện chu kỳ của Floyd\:Sử dụng con trỏ nhanh và chậm để phát hiện các chu kỳ trong chuỗi, tối ưu hóa độ phức tạp của không gian.
- Kiểm tra tính nguyên tố Miller-Rabin:Sau khi tìm được một thừa số, hãy kiểm tra xem nó có phải là số nguyên tố hay không để tránh việc phân tích thành thừa số không cần thiết.
- Hệ số đệ quy:Phân tích đệ quy các thừa số tìm được cho đến khi tất cả đều là số nguyên tố.
Độ phức tạp về thời gian:
- Phòng xét xử:O(√n), phù hợp với số nhỏ hoặc tìm nhanh các thừa số nhỏ.
- Pollard Rho:Thời gian dự kiến O(n^(1/4)), hiệu quả cao đối với các số có hệ số cỡ trung bình.
- Miller-Rabin:O(k log³n), trong đó k là số vòng thử nghiệm, được sử dụng để kiểm tra tính nguyên thủy.