Number Sieves — Volume 10 — Sieves in Cryptography

10.1 About This Volume

For half a century, factoring large numbers was a quiet specialty. D. H. Lehmer’s machines factored Mersenne numbers and tabulated pseudosquares for an audience of a few dozen number theorists, and the question of whether a 50-digit number could be split was of no interest to anyone else. In 1977 that changed overnight. A public-key cipher was published whose security rested on one assumption: that multiplying two large primes is easy, and getting them back from the product is not. From then on, every advance in factoring was also an advance in breaking codes, and the people who built factoring machines found themselves in the same business as the codebreakers of Bletchley Park — the story told in this site’s Enigma series.

This volume follows that story from Lehmer to the present. It is, at bottom, the story of one idea — throw away the numbers that cannot help — applied with more and more cunning. The bicycle-chain sieve threw away candidate answers. The modern factoring algorithms throw away candidate pieces of an answer, keeping only those that break cleanly into small primes, and then assemble the answer from millions of pieces. The step that does the throwing away is still a sieve, and it is still the step that takes almost all the time.

The volume covers: why factoring matters to cryptography, and the RSA-129 challenge; Maurice Kraitchik’s idea of combining squares, and Michael Morrison and John Brillhart’s continued fraction method; Carl Pomerance’s quadratic sieve, with a small example worked in full and checked in Python; John Pollard’s number field sieve, at the level of what it does rather than how its algebra works; the factoring records from 1970 to the 2026 factorisation of RSA-260 on GPUs; the special-purpose sieving machines Adi Shamir and others designed — including TWINKLE, an optoelectronic sieve that is a direct conceptual descendant of Lehmer’s photoelectric gear machine; discrete logarithms and the 2015 Logjam attack; today’s recommended key sizes; and Shor’s algorithm and post-quantum cryptography, which retire factoring as the basis of public-key security.

10.2 Why Factoring Became a Matter of Security

In April 1977 Ron Rivest, Adi Shamir and Leonard Adleman of MIT circulated a technical memo describing a public-key cryptosystem; the journal version appeared in Communications of the ACM in February 1978 (Rivest, Shamir and Adleman, “A method for obtaining digital signatures and public-key cryptosystems”). In outline:

• Choose two large primes p and q and multiply them to get the modulus n = pq.
• Choose an encryption exponent e, and compute a decryption exponent d from e, p and q.
• Publish n and e. Anyone can encrypt a message M as C = Mᵉ mod n.
• Only the holder of d can decrypt: M = Cᵈ mod n.

Computing d requires knowing p − 1 and q − 1, which requires knowing p and q. So anyone who can factor n can read every message sent to its owner and forge the owner’s signature. Nobody has proved that factoring is the only way to break RSA, but after almost fifty years no other general attack has been found.

The paper was candid about how hard its authors thought factoring was. It quoted the fastest method then known to them, an unpublished algorithm of Richard Schroeppel’s, and tabulated its running time at one microsecond per operation: 3.9 hours for a 50-digit number, 74 years for 100 digits, 3.8 billion years for 200 digits. It recommended that n be “about 200 digits long”.

The same year, Martin Gardner described the scheme in his “Mathematical Games” column in the August 1977 Scientific American, and the inventors offered a token US$100 prize to anyone who could decrypt a message enciphered with a 129-digit modulus — the number later called RSA-129. Carl Pomerance, writing in 1996, recalls that the column had estimated the number to be safe “for 40 quadrillion years (though other estimates around then were more modest)” (Pomerance, “A tale of two sieves,” Notices of the AMS 43 (1996) 1473–1485). (Pomerance dates the column to 1976; it was the August 1977 issue.)

RSA-129 was factored in April 1994 — 17 years, not 40 quadrillion — by a team led by Derek Atkins, Michael Graff, Arjen Lenstra and Paul Leyland, using about 1,600 computers belonging to some 600 volunteers on the Internet. The method was the quadratic sieve, the sieving took roughly 5,000 MIPS-years over about eight months, and the decrypted message read THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE (RSA numbers, Wikipedia). The two factors, of 64 and 65 digits, multiply back to RSA-129 exactly; that check was run for this volume in Python.

What changed between 1977 and 1994 was not mainly hardware. Computers were perhaps a few thousand times faster and the job was spread over 1,600 of them; but against Schroeppel’s estimate the gap was far larger than that. The difference was the algorithm, and the algorithm was a sieve.

10.3 Kraitchik’s Idea: Build a Square Out of Pieces

Fermat’s method (Volume 9) looks for a single a where a² − N is a perfect square. For large N with factors far apart, there is no hope of stepping to it. In the 1920s the Belgian mathematician Maurice Kraitchik — whose work on mechanical sieving appears in Volume 5 — saw that one square is not needed. It is enough to find several values whose product is a square.

The reason is a congruence. If X² ≡ Y² (mod N) but X is not ≡ ±Y, then N divides (X − Y)(X + Y) without dividing either factor, so gcd(X − Y, N) is a proper factor of N. Euclid’s algorithm computes that greatest common divisor almost instantly.

Pomerance’s essay gives Kraitchik’s method on N = 2,041. The values Q(x) = x² − 2,041 for x = 46, 47, 48, … are 75, 168, 263, 360, 459, 560, … — none is a square, so Fermat would still be searching. But four of them factor into small primes:

Table 1 — Pomerance's essay gives Kraitchik's method on N = 2,041. The values Q(x) = x² − 2,041 for x = 46, 47, 48, … are 75, 168, 263, 360, 459, 560, … — none is a square, so Fermat would still be searching. But four of them factor into small primes

x	Q(x) = x² − 2,041	Factorisation
46	75	3 × 5²
47	168	2³ × 3 × 7
49	360	2³ × 3² × 5
51	560	2⁴ × 5 × 7

Multiplied together they give 2¹⁰ × 3⁴ × 5⁴ × 7², in which every exponent is even — a square. So with X = 46 × 47 × 49 × 51 ≡ 311 (mod 2,041) and Y = 2⁵ × 3² × 5² × 7 ≡ 1,416 (mod 2,041), X² ≡ Y², and gcd(1,416 − 311, 2,041) = 13. So 2,041 = 13 × 157. (Every number here was re-run in Python.)

Everything in modern factoring is in that small example:

• Relations: values of a polynomial that factor completely over small primes — numbers that are smooth.
• A factor base: the list of small primes allowed (here 2, 3, 5, 7).
• Linear algebra modulo 2: choosing a subset of relations whose exponents add up to even numbers, which is a matter of solving equations in which every number is 0 or 1.
• A gcd at the end.

What Kraitchik lacked was a fast way to find the smooth values, and a fast way to do the linear algebra once there were thousands of them. Morrison and Brillhart’s 1975 paper on F₇ opens with an epigraph from Kraitchik: “Quand on a à étudier un grand nombre, il faut commencer par en déterminer des résidus quadratiques” — “When one has to study a large number, one must begin by determining its quadratic residues.” It is the same sentence that sums up Lehmer’s machines.

10.4 Continued Fractions: Morrison and Brillhart

The first method to make Kraitchik’s idea work by computer was the continued fraction method (CFRAC). It had been introduced by D. H. Lehmer and R. E. Powers in 1931 and then neglected: as Michael Morrison and John Brillhart put it, hand computers judged it of “little practical value because of its fallibility”, after “computing for hours on a desk calculator only to find, time after time, that every combination of numbers produced, failed to factor your number (’… your butterfly net was empty’)” (Morrison and Brillhart, Mathematics of Computation 29 (1975) 183–205).

The method generates its candidate numbers from the continued fraction expansion of √N (or √kN). The numbers it produces are smaller than 2√N — much smaller than Kraitchik’s x² − N — so each is more likely to be smooth. Morrison and Brillhart called the allowed primes the factor base and did the linear algebra mod 2 by Gaussian elimination. They spent the summer of 1970 programming the IBM 360/91 at UCLA, and the factorisation of the seventh Fermat number,

F₇ = 2¹²⁸ + 1 = 59,649,589,127,497,217 × 5,704,689,200,685,129,054,721,

“was obtained on the morning of September 13, 1970.” The paper is dedicated to D. H. Lehmer on his seventieth birthday, and it notes that Lehmer and his associates had, “over the last forty-five years”, built “various powerful machines to carry out the sieving process automatically”, with a new shift-register sieve, the SRS-181, “capable of processing 20,000,000 values per second”, then under construction at Berkeley.

CFRAC’s weakness was the step Kraitchik had found hard: each candidate had to be tested for smoothness by trial division — dividing by every prime in the factor base in turn. For a factor base of thousands of primes, that is thousands of divisions per candidate, and almost all candidates fail. Pomerance puts the state of the art plainly: “In 1970 it was barely possible to factor ‘hard’ 20-digit numbers. In 1980, in the heyday of the Brillhart-Morrison continued fraction factoring algorithm, factoring of 50-digit numbers was becoming commonplace.”

10.5 The Quadratic Sieve: Eratosthenes Returns

The step that replaced trial division came from looking back at the oldest sieve of all. Pomerance’s account of it is worth quoting at length:

It occurred to me early in 1981 that one might use something akin to the sieve of Eratosthenes to quickly recognize the smooth values of Kraitchik’s quadratic polynomial Q(x) = x² − n. … It should be noted that the sieve of Eratosthenes does more than find primes. Some crossed-off numbers are crossed off many times. For example, 30 is crossed off three times, as is 42, since these numbers have three prime factors. Thus we can quickly scan the array looking for numbers that are crossed off a lot and so quickly find the numbers which have many prime factors.

The key fact is the one that runs through every volume of this series. For a prime p, Q(x) = x² − N is divisible by p exactly when x² ≡ N (mod p). If N is a quadratic residue of p, that congruence has two solutions, r and p − r, and then Q(x) is divisible by p at x = r, r + p, r + 2p, … and at x = (p − r), (p − r) + p, … — two arithmetic progressions, every p-th place. That is a bicycle chain p links long with two pins in it. (If N is not a residue of p, p never divides Q(x), and p is left out of the factor base.)

So instead of dividing every Q(x) by every prime, the quadratic sieve does this:

1. Lay out an array, one cell per x, each starting at zero.
2. For each prime p in the factor base, find its two roots and add log p to every p-th cell along each progression. No division is done; the program simply jumps through the array.
3. After all primes have been processed, a cell’s total is roughly the logarithm of the smooth part of Q(x). Where the total is close to log Q(x), Q(x) is probably smooth. Only those cells are trial-divided.

Adding logarithms turns “is this number a product of small primes?” into “is this sum large?”, and the cost per cell falls from thousands of divisions to a handful of additions. As Pomerance notes, the total work for each prime is proportional to the length of the array divided by p, which summed over all primes is only about log log Y steps per cell.

The algorithm was first tried on a large number by Joseph Gerver, who factored a 47-digit Cunningham-project number. Pomerance had difficulty getting factorers to adopt it until, at a conference in Winnipeg in the fall of 1982, he persuaded Gus Simmons and Tony Warnock of Sandia National Laboratories to try it on their Cray; there Jim Davis and Diane Holdridge began setting records, and Davis found the first way to switch between several polynomials so that the values never grew too large. Refined into the multiple polynomial quadratic sieve (MPQS), the idea became standard. By 1990, Pomerance writes, the quadratic sieve “had doubled the length of the numbers that could be factored, the record having 116 digits”; by 1994 it had RSA-129. Arjen Lenstra and Mark Manasse took the step of distributing the sieving over the Internet, soliciting computer time from volunteers, which is how RSA-129 was done.

10.6 A Quadratic Sieve Small Enough to Check

The number from Volume 9’s Fermat example, N = 10,012,997, can be factored by the quadratic sieve in a few hundred cells. Every value below was computed for this volume in Python.

Step 1: the factor base. √N is about 3,164.3, so take Q(x) = (3,165 + x)² − N for x = 0, 1, 2, …, 399. Use primes up to 50, keeping only those for which N is a quadratic residue (only those can ever divide Q(x)): 2, 7, 11, 19, 23, 29, 31, 41, 43 — nine primes. The other primes below 50 (3, 5, 13, 17, 37, 47) can never divide any Q(x) and are dropped.

Step 2: the sieve. For each prime, the two roots give the starting positions of its two progressions:

Table 2 — Step 2: the sieve. For each prime, the two roots give the starting positions of its two progressions

p	Starting x values (mod p)		p	Starting x values (mod p)
2	0		29	10, 11
7	0, 5		31	8, 17
11	7, 10		41	2, 23
19	4, 12		43	36, 41
23	5, 13

So 7 marks x = 0, 5, 7, 12, 14, 19, …; 11 marks x = 7, 10, 18, 21, …; and so on. Each mark adds log₂ p to its cell. The first twelve cells after sieving:

Table 3 — So 7 marks x = 0, 5, 7, 12, 14, 19, …; 11 marks x = 7, 10, 18, 21, …; and so on. Each mark adds log₂ p to its cell. The first twelve cells after sieving

x	Q(x)	log₂ Q(x)	Sieve total (bits)
0	4,228	12.05	3.81
1	10,559	13.37	0.00
2	16,892	14.04	6.36
3	23,227	14.50	0.00
4	29,564	14.85	5.25
5	35,903	15.13	7.33
6	42,244	15.37	1.00
7	48,587	15.57	6.27
8	54,932	15.75	5.95
9	61,279	15.90	0.00
10	67,628	16.05	9.32
11	73,979	16.17	4.86

None of these is close to being accounted for. Across the whole array of 400 cells, the sieve totals look like the figure below.

Step 3: relations. Flagging every cell whose total is within 7 bits of log₂ Q(x) picks out 13 of the 400 cells. Trial division of just those 13 finds seven smooth values; an eighth (x = 243, where 7⁴ divides Q(x) but was counted only once) slips under the threshold, the usual price of a cheap test. Here are all eight smooth values in the range:

Table 4 — Step 3: relations. Flagging every cell whose total is within 7 bits of log₂ Q(x) picks out 13 of the 400 cells. Trial division of just those 13 finds seven smooth values; an eighth (x = 243, where 7⁴ divides Q(x) but was counted only once) slips under the threshold, the usual price of a cheap test. Here are all eight smooth values in the range

x	3,165 + x	Q(x)	Factorisation
40	3,205	259,028	2² × 7 × 11 × 29²
84	3,249	543,004	2² × 7 × 11 × 41 × 43
166	3,331	1,082,564	2² × 7 × 23 × 41²
194	3,359	1,269,884	2² × 7² × 11 × 19 × 31
243	3,408	1,601,467	7⁴ × 23 × 29
327	3,492	2,181,067	7 × 19 × 23² × 31
358	3,523	2,398,532	2² × 23 × 29² × 31
392	3,557	2,639,252	2² × 7 × 11² × 19 × 41

Step 4: linear algebra mod 2. Write each relation as a row of exponent parities (even = 0, odd = 1) across the nine primes. For x = 40 the row is (0, 1, 1, 0, 0, 0, 0, 0, 0): 7 and 11 to an odd power, everything else even. The task is to choose rows that add up to all zeros mod 2. Gaussian elimination over the eight rows finds one such combination: x = 40, 194 and 327. Their product is

Q(40) × Q(194) × Q(327) = 2⁴ × 7⁴ × 11² × 19² × 23² × 29² × 31²,

every exponent even.

Step 5: the two squares. X = 3,205 × 3,359 × 3,492 ≡ 4,667,002 (mod N), and Y = 2² × 7² × 11 × 19 × 23 × 29 × 31 ≡ 5,920,880 (mod N). Then X² ≡ Y² (mod N).

Step 6: the factor. gcd(X − Y, N) = 2,003, and N / 2,003 = 4,999.

The same answer Volume 9 reached by Fermat’s method, by a completely different road. The difference only shows on large numbers. Fermat’s method needs the two factors to be close; the quadratic sieve does not care where they are. On a 100-digit number, Fermat’s method is hopeless, while the quadratic sieve needs a factor base of tens of thousands of primes, an array of many millions of cells (processed in segments, exactly as Volume 3 describes for Eratosthenes), a few tens of thousands of relations, and a large sparse matrix — and spends almost all of its time in step 2.

10.7 The Number Field Sieve

The quadratic sieve’s values Q(x) grow like √N, and the larger the values, the rarer the smooth ones. The way forward was to find polynomials with much smaller values. In 1988 John Pollard circulated a letter describing how to do it for numbers of a special form, using arithmetic in an algebraic number field, and illustrated it — Pomerance notes the irony — with a factorisation of F₇, “the first major success of the continued-fraction factoring method, almost twenty years earlier.”

The idea, at the level needed here: choose a polynomial f of low degree (say 5 or 6) and a whole number m with f(m) ≡ 0 (mod N). Then two different “worlds” are linked — ordinary integers, and the algebraic numbers built from a root of f — and a single pair of integers (a, b) gives two numbers to test for smoothness: a − bm on the rational side, and a value of f’s homogenised form, F(a, b), on the algebraic side. If both are smooth, the pair is a relation. With enough relations, linear algebra mod 2 finds a subset whose product is a square on both sides at once; taking the two square roots and mapping both back to arithmetic modulo N gives X² ≡ Y² (mod N), and a gcd finishes the job as before. Both numbers to be tested are far smaller than the quadratic sieve’s Q(x), which is the whole gain.

The sieving step is Lehmer’s step again, in two dimensions. For each prime p and each root, the pairs (a, b) at which p divides the value lie on a lattice; the sieve steps across that lattice adding log p, and keeps only the cells that collect enough on both sides.

Hendrik Lenstra improved the method; with Arjen Lenstra and Mark Manasse he began factoring numbers from the Cunningham tables with it, and in 1990 the four of them, with Pollard, completed the ninth Fermat number, F₉ = 2⁵¹² + 1, a 155-digit number — “on approximately 700 workstations scattered around the world, and in one of the final stages a supercomputer was used. The entire factorization took four months” (Lenstra, Lenstra, Manasse and Pollard, “The factorization of the ninth Fermat number,” Mathematics of Computation 61 (1993) 319–349). F₉ is the product of primes of 7, 49 and 99 digits.

That was the special number field sieve, which needs N to be close to a power. Extending it to arbitrary N — the general number field sieve — took several more years of work by many hands. In the spring of 1996 it split the 130-digit challenge number RSA-130, Pomerance writes, “in about 15% of the time the quadratic sieve would have taken,” and since then every general factoring record has been set with it.

10.8 The Records

The table below lists general-purpose factoring records — numbers with no special form, chosen to be as hard as RSA moduli — from F₇ to the present. RSA challenge numbers are named for their decimal digits up to RSA-500 and their bits afterwards (RSA-576, RSA-768). Dates are from the RSA numbers table; computing costs from the papers cited.

Table 5 — The Records

Number	Digits	Date	Method	Notes
F₇	39	13 Sep 1970	CFRAC	IBM 360/91, UCLA
RSA-100	100	Apr 1991	QS	Arjen Lenstra
RSA-129	129	Apr 1994	QS	~1,600 machines, ~5,000 MIPS-years
RSA-130	130	Apr 1996	NFS	first record by general NFS
RSA-155 (512 bits)	155	22 Aug 1999	NFS	first 512-bit RSA modulus factored
RSA-200	200	May 2005	NFS
RSA-768	232	12 Dec 2009	NFS	almost 2,000 single-core years
RSA-240	240	Nov 2019	NFS (CADO-NFS)	~1,000 core-years
RSA-250	250	Feb 2020	NFS (CADO-NFS)	~2,700 core-years
RSA-260 (862 bits)	260	3 Sep 2026	NFS on GPUs (modified CADO-NFS)	~4,900 GPU-days

RSA-768 was factored by Thorsten Kleinjung and colleagues from several institutions. The sieving “was done on many hundreds of machines and took almost two years”; the whole computation was “the equivalent of almost 2000 years of computing on a single core 2.2GHz AMD Opteron”, on the order of 2⁶⁷ instructions (Kleinjung et al., “Factorization of a 768-bit RSA modulus,” IACR ePrint 2010/006). The paper concludes that “even for short-term protection of data of little value, 768-bit RSA moduli can no longer be recommended.”

RSA-240 (795 bits) and RSA-250 (829 bits) were factored in 2019 and 2020 by Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann with the open-source CADO-NFS software. Their paper puts the total for RSA-240 at “about 1000 core-years”, measured on a 2.1 GHz Intel Xeon Gold 6130; its breakdown is 76 core-years of polynomial selection, 794 core-years of sieving and about 83 for the matrix. RSA-250 took “roughly 2700 core-years” (Boudot et al., “Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment,” CRYPTO 2020; arXiv 2006.06197). For RSA-240, sieving was 83 percent of the effort.

RSA-250 held the record for six and a half years. On 3 September 2026 Eric Lu of Cognition factored RSA-260, a 260-digit (862-bit) number, into two 130-digit primes (Cognition, “Factoring RSA-260”; RSA Factoring Challenge, Wikipedia). The method was still the general number field sieve, in a heavily modified CADO-NFS ported to GPUs — the write-up describes “no new algorithmic advances”, only “good old performance engineering”, with Cognition’s Devin AI coding agent doing much of the measurement, cluster operation and optimisation. The computation took about 4,900 GPU-days on NVIDIA B200, GB200 and GB300 nodes, mostly spare cluster capacity: roughly 643 GPU-days of polynomial selection, 3,813 of sieving and 467 of linear algebra. Sieving was again more than three-quarters of the work. The post estimates the market cost at about $400,000. Fifty-six years after F₇, the expensive step in the largest public factorisation is still a sieve.

The slope of that chart is gentle: from 100 to 260 digits in the thirty-five years since 1991. Each gain has needed both faster hardware and better algorithms. A 2048-bit modulus, at 617 digits, is so far above the curve that no extrapolation of classical methods reaches it.

10.9 Sieving Machines: TWINKLE, TWIRL and SHARK

Since sieving dominates the cost, it is natural to ask whether a special machine could do it faster than general-purpose computers — the question Lehmer had answered with chains and gears. In the 1980s a few were built: the “Georgia Cracker”, a continued-fraction processor built by Jeff Smith and Sam Wagstaff, had “some limited success”, and “Quasimodo”, a quadratic sieve processor designed by Smith, Randy Tuler and Pomerance, “was built but never functioned properly” (Pomerance 1996). Then, from 1999, came a series of designs from cryptographers that were analysed in detail and never built.

10.9.1 TWINKLE (1999): an optoelectronic sieve

At Eurocrypt ‘99 in May 1999 Adi Shamir presented TWINKLE — “The Weizmann Institute Key Locating Engine” — and published it at CHES 1999 as “Factoring large numbers with the TWINKLE device.” Bruce Schneier, reporting it in his newsletter, observed that “a mechanical-optical machine built by D.H. Lehmer in the 1930s did much the same thing” (RISKS Digest 20.38). The resemblance is close enough to describe one machine in terms of the other.

Arjen Lenstra and Shamir’s follow-up analysis summarises the design (Lenstra and Shamir, “Analysis and optimization of the TWINKLE factoring device,” Eurocrypt 2000). A conventional sieve, they explain, uses space (memory) to represent the sieve interval and time (clock cycles) to loop over the primes. TWINKLE reverses the roles: “it uses space to represent the (p, r) pairs, and time to loop over the sieve interval.” Each prime gets its own cell on the wafer, holding a counter loaded with the prime and its root. On every clock tick, every cell counts down at once; when a cell’s counter hits zero, its LED flashes, with brightness proportional to log p, and the counter reloads. The photodetector sums the light of every LED that flashes on that tick. If the total exceeds a threshold, the current sieve position is reported as probably smooth.

That is a Lehmer sieve. In the gear machine, each gear is a counter of length p; a hole is a “flash”; and the photocell responds only when all the holes line up — a logical AND. In TWINKLE the summing is analogue rather than all-or-nothing, because the quadratic and number field sieves ask “are enough primes present?” rather than “are all conditions met?” The patent’s own drawings show the swap: the left panel of the figure below is the PC — memory locations across, primes processed one at a time down — and the right is TWINKLE, with one LED per prime and time running across.

The patent claims that gallium arsenide LEDs “can be clocked at rates exceeding 1 gigahertz without difficulty”, against about 100 MHz for the memory of a PC of the time, and that one device “can test the smoothness of 100,000,000 modular squares over a prime base of 200,000 primes in less than 0.1 seconds” — 50 to 100 times faster than conventional sieving. Lenstra and Shamir’s detailed analysis was more sober: a TWINKLE-assisted factorisation of a 768-bit number would be “difficult but doable in about 9 months … by a large organization which can use 80,000 standard Pentium II PC’s and 5,000 TWINKLE devices.” And they stated plainly: “the TWINKLE device itself has not been built so far, and thus its feasibility, performance, and cost are open to debate.” It never was built.

10.9.2 TWIRL (2003) and its successors

Four years later Shamir and Eran Tromer replaced the optics with ordinary silicon. TWIRL — “The Weizmann Institute Relation Locator” — keeps TWINKLE’s idea of exchanging time and space but processes thousands of sieve positions per clock through a long pipeline, with primes of different sizes handled by different kinds of station. Its designers estimated that the sieving step for a 512-bit RSA key “can be completed in less than ten minutes by a $10K device”, and that for 1024-bit keys it “can be completed in less than a year by a $10M device”, adding that “this raises some concerns about the security of this key size” (Shamir and Tromer, “Factoring large numbers with the TWIRL device,” CRYPTO 2003). It too was never built.

Eran Tromer’s annotated taxonomy of special-purpose cryptanalytic devices lists the others: mesh-based sieving designs by Willi Geiselmann and Rainer Steinwandt (2003–2004), SHARK by Jens Franke, Thorsten Kleinjung, Christof Paar, Jan Pelzl, Christine Priplata and Colin Stahlke (2005), and Daniel Bernstein’s 2001 mesh circuit for the matrix step — all designs and cost estimates, none built. The one built sieving device on that list from the period is CAIRN 2, an FPGA machine by Tetsuya Izu and colleagues (CHES 2007) that sieved a 423-bit special-form number in 30 days. The same taxonomy places TWINKLE as the first of the modern devices, and Lehmer’s chain, gear and film sieves among their historical ancestors, alongside Carissan’s 1919 machine.

The pattern is telling. Lehmer could build a special machine more cheaply than he could buy general computing time. By 2000, general-purpose processors were so cheap and plentiful that a special device had to beat thousands of them on cost, and no design was certain enough of doing so to be worth fabricating — at least in public. Every record in the table above was set on general-purpose hardware — CPUs until 2020, and for RSA-260 the same GPUs that are bought by the hundred thousand for other work.

10.10 Discrete Logarithms and Logjam

Factoring is not the only problem the number field sieve solves. The Diffie–Hellman key exchange, published in 1976, lets two parties agree on a secret over an open channel. Each picks a secret exponent and publishes g raised to it modulo a prime p; each can then compute g raised to the product of both secrets, and an eavesdropper cannot — unless she can compute a discrete logarithm, recovering an exponent from a power. The best classical algorithm for discrete logarithms modulo a large prime is a variant of the number field sieve, and it has a property with large practical consequences: almost all the work depends only on the prime p, not on the particular key exchange. A single massive precomputation for one prime makes every later exchange that uses that prime cheap to break.

In 2015 a team of fourteen researchers showed what that meant in practice (Adrian et al., “Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice,” ACM CCS 2015; summary at weakdh.org). Their Logjam attack exploited a flaw in TLS — the protocol that secures web traffic — that lets a man-in-the-middle downgrade a connection to “export-grade” 512-bit Diffie–Hellman, a deliberately weakened mode left over from 1990s US export rules. They found that 8.4 percent of the Alexa top million HTTPS sites supported it, and that 82 percent of the vulnerable servers used the same 512-bit prime.

They then ran the number field sieve against the most common primes. For each, sieving took about 15 hours on 2,000–3,000 CPU cores (21,400 core-hours), and the matrix step 120 hours on a cluster; “the wall-clock time for each precomputation was slightly over one week.” After that, an individual discrete logarithm — the key for one connection — took a median of about 70 seconds. Extrapolating to 1024-bit primes, they estimated the precomputation at about 45 million core-years: huge, but “plausibly within NSA’s resources” for “at least a small number of 1024-bit Diffie-Hellman groups,” with special-purpose sieving hardware of the TWIRL kind cutting the cost further. Browsers and servers dropped export-grade cryptography, and the advice to stop sharing small fixed Diffie–Hellman primes became standard.

10.11 Key Sizes Today

How large must a modulus be? The US National Institute of Standards and Technology answers in terms of security strength: the number of bits of a symmetric key that would take equivalent effort to break by brute force. Its key-management guideline tabulates the equivalences (NIST SP 800-57 Part 1 Rev. 5 (2020), Table 2):

Table 6 — How large must a modulus be? The US National Institute of Standards and Technology answers in terms of security strength: the number of bits of a symmetric key that would take equivalent effort to break by brute force. Its key-management guideline tabulates the equivalences ([NIST SP 800-57 Part 1 Rev. 5 (2020), Table 2](https://doi.org/10.6028/NIST.SP.800-57pt1r5))

Security strength	Symmetric cipher	RSA modulus (k)	Finite-field DH/DSA (L)	Elliptic curve (f)
≤ 80 bits	2TDEA	1,024	1,024	160–223
112 bits	3TDEA	2,048	2,048	224–255
128 bits	AES-128	3,072	3,072	256–383
192 bits	AES-192	7,680	7,680	384–511
256 bits	AES-256	15,360	15,360	512+

The asymmetry is the number field sieve’s doing. Because NFS factors in sub-exponential time, the RSA modulus must grow much faster than the symmetric key: doubling the security strength from 128 to 256 bits multiplies the RSA modulus by five. Elliptic-curve keys, which have no known sieve-based attack, grow only in proportion. The table carries an asterisk on the RSA and elliptic-curve columns: “The security-strength estimates will be significantly affected when quantum computing becomes a practical consideration.”

10.12 Shor’s Algorithm and the End of the Line

In 1994 Peter Shor, then at AT&T Bell Laboratories, showed that a quantum computer could factor integers and compute discrete logarithms in polynomial time — an exponential speed-up over every classical method in this volume (Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” arXiv quant-ph/9508027). Shor’s algorithm does not sieve at all. It turns factoring into finding the period of the function x ↦ aˣ mod N, and finds the period with a quantum Fourier transform. In a sense it is the ultimate version of Lehmer’s insight about periodicity: a sieve exploits the fact that divisibility by p repeats every p steps; Shor’s algorithm exploits the period of an exponential, all periods at once.

No quantum computer yet built can run it on a number of cryptographic size. But the estimates of what would be needed have fallen steadily. In May 2025 Craig Gidney of Google Quantum AI estimated that a 2048-bit RSA integer could be factored in less than a week by a machine with fewer than a million noisy qubits, down from about 20 million in his 2019 estimate with Martin Ekerå (Gidney, “How to factor 2048 bit RSA integers with less than a million noisy qubits,” arXiv 2505.15917). Data encrypted today could be recorded now and decrypted when such a machine exists, so the replacement had to begin before it does.

On 13 August 2024 NIST published its first three post-quantum standards (NIST announcement):

• FIPS 203, ML-KEM (from CRYSTALS-Kyber): key encapsulation, the replacement for RSA and Diffie–Hellman key exchange, based on lattice problems;
• FIPS 204, ML-DSA (from CRYSTALS-Dilithium): lattice-based digital signatures;
• FIPS 205, SLH-DSA (from SPHINCS+): signatures based only on hash functions, as a backup built on different mathematics.

In November 2024 NIST published a draft transition plan, NIST IR 8547, proposing that RSA, elliptic-curve and finite-field Diffie–Hellman at the 112-bit security level be deprecated after 2030, and all quantum-vulnerable public-key algorithms disallowed after 2035 (NIST IR 8547, initial public draft). None of the new algorithms rests on factoring or discrete logarithms, and no sieve is known to help against them.

10.13 The Idea of Throwing Numbers Away

Seen from the end, the history in this volume is continuous with the history of the machines. Lehmer’s chains and gears stepped through candidates and threw away every one that failed a congruence. Kraitchik and Morrison–Brillhart showed that a factor could be built from many small pieces rather than found in one piece. Pomerance noticed that Eratosthenes’ sieve, run with logarithms instead of crossings-out, finds the pieces at almost no cost per candidate. Pollard moved the pieces into a number field where they are smaller and more plentiful. Shamir put the sieve back into hardware, with LEDs where Lehmer had holes in gears and a photodetector where Lehmer had a photocell. At every stage the expensive step was the same: march through an arithmetic progression, mark every p-th place, and keep only the positions that collect enough marks.

The quantum algorithm that ends the story does not throw numbers away; it keeps them all, in superposition, and reads off their period. The post-quantum standards do not involve primes at all. Factoring will remain one of the central problems of number theory and computation — and the sieve, in its many forms, its central tool — but after 2035, if NIST’s plan holds, it will no longer be what stands between an eavesdropper and the world’s secrets. The next four volumes go back to the beginning, to the machines themselves, and to building them.

---

Next — Volume 11: Building the Bicycle-Chain Sieve. From history to the workbench: roller chain cut to exact lengths, sprockets on one shaft, tabs at the acceptable residues, a contact over every chain, and a procedure for loading and running a problem.