SievesMethods

Every classical method since 1926 is the same trick with better tools: find two numbers whose squares agree when divided by N, and the greatest common divisor does the rest. Here is the trick on a number small enough to do by hand, and four old methods racing on numbers of different shapes.

Four methods, one number

the number

Bars are steps taken, on a log scale. Each method gives up at three million steps. Pick a different number and a different method wins — that is the lesson. Trial division likes a small factor; Fermat likes two close ones; p − 1 likes a factor whose neighbour is made of small primes; rho does not care and is slow. The number field sieve, below, is what you use when you know nothing about the shape.

Two squares that agree

Fermat's idea needs N itself to be a² − b². Kraitchik's improvement [9] is that you only need two numbers whose squares leave the same remainder when divided by N:

x² ≡ y² (mod N) ⇒ N divides (x − y)(x + y)

Reading it: if x² and y² differ by a multiple of N, then N divides the product on the right — and unless x ≡ ±y, N has to share part of itself with each bracket. gcd(x − y, N) is a factor.

Finding such a pair directly is as hard as factoring. The trick is to build one. Take x just above √N, so that x² − N is small, and keep the ones that break into small primes — the smooth ones. Then multiply a handful together so that every prime appears an even number of times: the product is a square by construction.

Carl Pomerance's example [19], N = 1649:

41² = 1681 = 1649 + 32, and 32 = 2⁵
43² = 1849 = 1649 + 200, and 200 = 2³ · 5²

Reading it: two squares just above N whose leftovers are made of small primes

(41 · 43)² ≡ 32 · 200 = 6400 = 80² (mod 1649)

Reading it: multiply the two: the left is a square, and the right — 2⁸ · 5² — is a square too. So X = 41 · 43 = 1763 ≡ 114, Y = 80.

gcd(114 − 80, 1649) = gcd(34, 1649) = 17, 1649 = 17 × 97

Reading it: Euclid's algorithm, two thousand years old, finishes the job.

Try it on a number

The parities column is what the linear algebra works on: a row of 0s and 1s, one per small prime, saying whether that prime appears an odd number of times. A set of rows that adds to all zeros (mod 2) is a square. About half the squares found are duds — X ≡ ±Y — and then you take the next.

From the trick to the records

Dixon, 1981 [17] — pick random x, keep the smooth x² mod N, do the linear algebra. The first method with a proved sub-exponential running time.

The quadratic sieve, 1981 [18][19] — do not test each x² − N for small factors one at a time. Notice that if p divides x² − N then it also divides (x + p)² − N, so a prime p marks every p-th entry in the row — the sieve of Eratosthenes again, run over the values x² − N. That is where the name comes from and why it was ten to a hundred times faster than what came before. It set every record from 1983 to 1994, including the 129-digit number from Martin Gardner's column [23].

The number field sieve, 1988–1993 [22][21] — the same plan, but the smooth values are found in a larger number system than the integers, where they are far smaller and so far more often smooth. The price is a lot of algebra to get back to ordinary integers at the end. It is the fastest method known for numbers of no special form, and every record since 1996 is a run of it — the 2019, 2020 and 2026 records all with the same open-source program, CADO-NFS [28][26][99][101].

The elliptic curve method, 1985 [20] — a different family: its cost depends on the size of the factor it finds, not the size of N. It is the tool for pulling a 30-digit factor out of a 300-digit number, and it is the first place the curves of the wallet page appear in factoring.

What none of them do is scale kindly. The next page draws the cost curve.