Code python của thuật toán Pollard's Rho

Để phân tích một số N (ví dụ $798564133$) ra thừa số nguyên tố (mà máy tính Casio fx-880BTG) không thực hiện, các bạn copy đoạn code sau đây dán vào Python Online (bấm vào đây) . Dán đè lên code mẫu của python online. Sau đó bấm Run

import math
# Khởi tạo các thông số theo đúng bài toán của thầy
N = 798564133
x = 2  # Vị trí ban đầu của Rùa
y = 2  # Vị trí ban đầu của Thỏ
c = 1  # Hằng số c trong hàm f(x) = x^2 + c
# Hàm sinh chuỗi f(x) = (x^2 + c) mod N
def f(val):
    return (val**2 + c) % N
print(f"BẮT ĐẦU CHẠY THUẬT TOÁN POLLARD'S RHO CHO N = {N}")
print("-" * 90)
print(f"{'Bước':<8} | {'Rùa (x)':<15} | {'Thỏ (y)':<15} | {'Hiệu số |x - y|':<18} | {'GCD(|x-y|, N)': 1)
while g == 1:
    step += 1
    x = f(x)       # Rùa đi 1 bước
    y = f(f(y))    # Thỏ đi 2 bước
    diff = abs(x - y)
    g = math.gcd(diff, N)
    # In ra kết quả của bước hiện tại
    print(f"{step:<8} | {x:<15} | {y:<15} | {diff:<18} | {g:<15}")
print("-" * 90)
print(f"Thuật toán dừng lại ở Bước {step}!")
print(f"Tìm thấy ước số thực sự của {N} là: {g}")
print(f"Phép chia kiểm tra: {N} / {g} = {N // g}")

Để chụp hình minh hoạ, chúng tôi cho giá trị đầu tiên của Rùa và Thỏ là 7 (do Thầy Trầm Thanh Phong (Vĩnh Long) phát hiện) để sau 28 bước có kết quả. Nhưng thông thường ta nên chọn giá trị đầu tiên là 2 (Thỏ) và 2 (Rùa) để chúng chạy trên đường thẳng trước khi vào vòng tròn (chữ $\rho$) , chấp nhận tới bước 116 mới lộ diện thừa số nguyên tố.

About TS. Nguyễn Thái Sơn

Nguyên trưởng Khoa Toán-Tin học ĐHSP TP HCM (1999-2009). Nguyên Giám đốc- Tổng biên tập NXB ĐHSP TP HCM (2009-2011). Nguyên Tổng thư ký Hội Toán học TP HCM (2008-2013).