Làm gì khi máy tính Casio fx-880BTG xuất ra thông báo chẳng hạn như sau

Khi gặp số $a$ trong ngoặc đơn như trên, ta thực hiện phép thử $(-1)^{\frac{a^2-1}{8} }$, nếu kết quả khác 1 thì $a$ là hợp số . Muốn phân tích $a$ ra thừa số nguyên tố ta dùng thuật toán thử chia (trivial division) (nếu $\sqrt{a}$ không quá lớn), dùng thuật toán Pollard’s Rho trong trường hợp ngược lại.
 

Đối với máy tính Casio fx-580VNX, thuật toán Pollard’s Rho thực hiện như sau:
 

1. Gán số $8788763$ vào biến nhớ $z$ .
2. Nhập lên màn hình trên một dòng:
   $A=A^2+1-\text{z}\text{Int}\dfrac{A^2+1}{z}:B=B^2+1-\text{z} \text{Int}\dfrac{B^2+1 }{\text{z} }: B=B^2+1-\text{z} \text{Int}\dfrac{B^2+1 }{\text{z} }:\text{GCD}(|A-B|, \text{z}) $

 

3. Bấm CALC, nhập $A=2$, bảo lưu $z$ (nghĩa là bấm mũi tên xuống) và nhập $B=2$, sau đó nhấn phím 4 lần, các lần sau bấm nhanh phím 5 lần, Nếu thấy kết quả là $1$ thì tiếp tục cho đến khi thấy GCD lớn hơn 1 thì đó chính là thừa số nguyên tố thứ nhất. Muốn tìm thừa số nguyên tố thứ hai ta lấy $z$ chia cho thừa số nguyên tố thứ nhất. Kiểm tra xem thừa số thứ hai có là số nguyên tố không.
4. Nếu thừa số thứ hai này là số nguyên tố thì kết luận:$8788763=1697\times 5179$.

Đọc kỹ thuật toán trước khi xem clip. Khi xem clip nếu cần có thể dừng/pause (để quan sát), nếu chưa theo dõi kịp có thể dừng rồi “tua” lại.
 

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