A nontrivial congruence of squares splits (QS / GNFS)
ProvedPolyTimeFactorization.congruent_squares_splitfactorizationnumber-theorysieve
Let and . If but and , then
so is a nontrivial divisor of .
This is the splitting step that concludes both the quadratic sieve and the number field sieve: once a congruence of squares is found that is nontrivial modulo , a single gcd reveals a proper factor. The two exclusions are exactly what rules out the trivial factors and .
Preamble
import Mathlib
Formal statement
namespace PolyTimeFactorization
theorem congruent_squares_split (n : ℕ) (x y : ℤ) (hn : 0 < n)
(hsq : (n : ℤ) ∣ x ^ 2 - y ^ 2)
(hxy : ¬ (n : ℤ) ∣ x - y) (hxy' : ¬ (n : ℤ) ∣ x + y) :
1 < Int.gcd (x - y) (n : ℤ) ∧ Int.gcd (x - y) (n : ℤ) < n := by sorry
end PolyTimeFactorizationSource
C. Pomerance, The quadratic sieve factoring algorithm, EUROCRYPT '84, LNCS 209 (1985), 169-182, https://doi.org/10.1007/3-540-39757-4_17 ; J. P. Buhler, H. W. Lenstra Jr., C. Pomerance, Factoring integers with the number field sieve, LNM 1554 (1993), 50-94, https://doi.org/10.1007/BFb0091539 (the congruence-of-squares principle)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.