Phân tích một số “rất lớn” ra thừa số nguyên tố.

Một số “rất lớn” như số có 13 chữ số $7986636071569$ khi phân tích ra thừa số nguyên tố có hai tình trạng thường gặp.

1. Một thừa số nguyên tố rất nhỏ và một (hay nhiều) thừa số nguyên tố “rất lớn”.

2. Hai thừa số nguyên tố rất lớn, gần nhau (nhưng có thể cách nhau cả ngàn số) và ở giữa, nghĩa là gần $\sqrt{\text{số đó}}$.
 
Tình huống 1. Có một thừa số nguyên tố rất nhỏ (nhỏ hơn 200) có 45 số như vậy, vừa khít một bảng tính. Để làm bài toán này ta dùng thuật toán chia thử (Trial Division) , gán số đã cho vào biến nhớ $A$ và sử dụng một bảng tính. Cột A nhập các số
 
lẻ từ $3$ đến $91$, cột B điền công thức , kết quả . Hiệu bằng $0$, nghĩa là phép chia có thương bằng $0$. Vậy $17$ là một thừa số nguyên tố.
 
Tiếp theo ta thay số $3$ ở $A_1$ thành $93$ (tiếp theo của $91$), bảng tính cập nhật . Vậy $101$ là thừa số nguyen tố tiếp theo.

Cuối cùng .
 
Vậy $7986636071569=17\times 101\times 277\times 317\times 52973$
 

Lưu ý: Một trang bảng tính có 45 số lẻ, hai số ở hai biên cách nhau 90 đơn vị nên nhảy từ $101$ đến $277$ và $317$ là không khó khăn gì (dù không cần thiết) .

 
 
Tình huống 2. Hai thừa số nguyên tố rất lớn, gần nhau. Ta chỉ xét những số không quá 10 chữ số, ví dụ $8788763$.
 

Gán số $8788763$ vào biến nhớ A . Gán hàm số $f(x)=x^2+1-A \text{Int}\dfrac{x^2+1}{A}$ vào
 
biến nhớ $f(x)$ .
 
Mở một bảng tính, nhập số $2$ vào $A_1$ và $B_1$ (xuất phát điểm của Rùa và Thỏ) .
 
Tại $A_2$ điền công thức cho Rùa: (nhiều hơn $20$ sợ tràn biến nhớ).
 
Tại $B_2$ điền công thức cho Thỏ: .
 
Tại $C_2$ điền công thức tính ƯCLN của hiệu giữa Rùa và Thỏ với $A$: $\qquad \text{GCD(Abs(}A_2-B_2),A)$.
.
 
Duyệt cột $C$ đến khi thấy một số lớn hơn $1$ và nhỏ hơn $A$ thì đó là thừa số nguyên tố thứ nhất: .
 
Thừa số nguyên tố thứ hai:
 

Vậy $8788763=1697\times 5179$.

Lưu ý: Thuật toán vừa nêu gọi là Thuật Toán Pollard’s Rho , thuật toán này chạy nhanh hơn thuật toán chia thử.
 

Thuật toán Pollard’s Rho được phát minh năm 1975 bởi Pollard.
 
Thuật toán này đến ngày nay vẫn còn được nhiều nghiên cứu viên quan tâm
 
Bấm vào hình sẽ dẫn tới trang chủ của VIASM.
 

Vậy $798564133=31081\times 25693$.
 

Cám ơn Thầy Phong đã kiên trì dò tìm xuất phát điểm của Rùa và Thỏ.

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).