Pollard's criterion
ProvedPolyTimeFactorization.pollard_p_minus_onefactorizationnumber-theory
Pollard's criterion. Let be a prime dividing , let with , and let . Put . If divides — equivalently, is -power-smooth, meaning every prime power satisfies — then
Thus a single modular exponentiation followed by a gcd reveals the factor , provided is sufficiently smooth. This is the correctness guarantee of Pollard's method and follows from Fermat's little theorem. The hypothesis concerns , not .
Preamble
import Mathlib
Formal statement
namespace PolyTimeFactorization
theorem pollard_p_minus_one (n p a B : ℕ) (hp : p.Prime) (hpn : p ∣ n)
(ha : 1 < a) (hpa : ¬ p ∣ a) (hB : 1 ≤ B)
(hsmooth : p - 1 ∣ (Finset.Icc 1 B).lcm id) :
p ∣ Nat.gcd (a ^ (Finset.Icc 1 B).lcm id - 1) n := by sorry
end PolyTimeFactorizationSource
J. M. Pollard, Theorems on factorization and primality testing, Math. Proc. Cambridge Philos. Soc. 76 (1974), 521-528 (the p-1 method), https://doi.org/10.1017/S0305004100049252 ; standard formulation: https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.