Tại sao giai thừa được sử dụng trong thuật toán $p - 1$ của Pollard?

Định lý Fermat Nằm đằng sau sơ đồ phân tích thừa số thứ hai này, được gọi là phương pháp thăm dò ý kiến ​​p-1.

• giả sử số nguyên hỗn hợp lẻ n được phân tích thành nhân tử có ước nguyên tố n, với tính chất p-1 là tích của các số nguyên tố tương đối nhỏ. Gọi q là một số nguyên bất kỳ sao cho (p-1)|q. Chẳng hạn q có thể là k! hoặc bội số chung nhỏ nhất của k số nguyên dương đầu tiên, trong đó k được lấy đủ lớn. chọn 1<a<p-1
• $${m\equiv a^q \equiv a^{(p-1)j}\equiv 1^j \equiv1(modp)}$$ ngụ ý p| (m-1), lực lượng này ${gcd(m-1,n)>1}$
• Nhưng điều quan trọng cần lưu ý ở đây là, nếu ${gcd(m-1,n)=1}$, thì bạn nên quay lại và chọn giá trị khác của a.
• Phương pháp này có thể thất bại nếu q (k!) không đủ lớn; đó là nếu p-1 chứa thừa số nguyên tố lớn hoặc một số nguyên tố nhỏ xảy ra với lũy thừa lớn, do đó tốt hơn là chọn k!, thay vì đoán bất kỳ số lớn mới nào mỗi khi chúng ta nhận được ${gcd(m-1,n)=1}$, do đó giai thừa là lựa chọn tốt hơn và có thể tăng xác suất tìm thấy nếu một thừa số là thừa số nguyên tố lớn.