Pollard's rho: the collision lemma
ProvedPolyTimeFactorization.pollard_rho_collisionfactorizationnumber-theory
The collision lemma behind Pollard's rho method. Let be a prime properly dividing the composite (so ), and let satisfy but . Then
so the gcd yields a nontrivial factor of .
In the rho method the iterates of a polynomial modulo eventually collide modulo — heuristically after steps, by the birthday paradox — while remaining distinct modulo . This lemma is the rigorous step that converts such a collision into a factor.
Preamble
import Mathlib
Formal statement
namespace PolyTimeFactorization
theorem pollard_rho_collision (n p : ℕ) (x y : ℤ) (hp : p.Prime) (hpn : p ∣ n)
(hlt : p < n) (hcol : (p : ℤ) ∣ x - y) (hncol : ¬ (n : ℤ) ∣ x - y) :
1 < Int.gcd (x - y) (n : ℤ) ∧ Int.gcd (x - y) (n : ℤ) < n := by sorry
end PolyTimeFactorizationSource
J. M. Pollard, A Monte Carlo method for factorization, BIT 15 (1975), 331-334 (the gcd step of the rho method), https://doi.org/10.1007/BF01933667
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.