QUADRATIC SIEVE manufacture a congruence, let gcd finish
Factor n without ever guessing a factor. Sieve the values Q(a) = a² − n near √n for ones that are smooth (factor completely over a small prime base); combine two whose product is a perfect square, giving x² ≡ y² (mod n); then gcd(x−y, n) splits n at least half the time (spare relations cover the misses). The fastest classical method below ~100 digits.
THE TECHNIQUE sieve for smooth squares, combine, gcd
Pick a factor base of small primes. For a just above √n, compute Q(a)=a²−n and trial-divide by the base; keep the smooth ones. Two smooth relations whose combined prime exponents are all even multiply to a perfect square: set x = ∏a, y = √∏Q, and gcd(x−y, n) splits n. Factor a number and watch the relations assemble. live demo
HISTORY & CREDIT the heart is Kraitchik's
“Fastest factoring algorithm ever” — only everof its era (early-80s to the mid-90s: RSA-129 still fell to MPQS in 1994; GNFS took the record at RSA-130 in 1996); it stays simplest below ~100 digits. cited
c.1643 · Fermat’s difference-of-squares n = u² − v² — the direct ancestor, fast only when the factors are close. 1920s · Maurice Kraitchik — the decisive idea under all modern factoring: don’t demand u²−v²=n, just u² ≡ v² (mod n). This congruence-of-squares is the actual heart of QS. c.1977 · Richard Schroeppel’s linear sieve (never formally published) — the explicit parent QS refines. 1981 · Carl Pomerance invents the quadratic sieve at Georgia; Dixon (1981) gives the rigorously-proven random-squares cousin (QS itself has only a heuristic runtime). MPQS (Davis-Holdridge / Montgomery) set records; RSA-129 fell to double-large-prime MPQS in 1994.
Its speed is conjectural — it trades Dixon’s proof for practical speed. Pomerance, 1981
RECOMMEND FOR I-13 sieve + gcd run; the GF(2) solve wants a matrix
The congruence-of-squares core runs end to end on the corpus — two smooth relations combine into a factor:
$ i13 run qs.i13 # n=1649
a=41: Q=32=2^5 a=43: Q=200=2^3*5^2 (same parity -> product is a square)
x=41*43=114 y=sqrt(32*200)=80 114^2 = 80^2 = 1453 (mod 1649)
gcd(114-80,1649)=17 gcd(114+80,1649)=97 1649 = 17 x 97
Recommend: the congruence-of-squares core is LIT — the sieve interval is an f64 array, trial division and smoothness are integer mod, the combine is a bignum multiply, and the split is Euclid’s gcd (dart 027) (verified 114² ≡ 80² ≡ 1453 (mod 1649), gcd → 17 and 97). Note: the frontier is the general step this toy skips — choosing which relations to combine is Gaussian elimination over GF(2) on the exponent-parity vectors, a genuine 2-D bit matrix (PS-004). Two hand-picked relations dodge it; the real sieve cannot.