Number Sieves — Volume 1 — Machines That Throw Numbers Away

1.1 About This Volume

This is the entry point to a fourteen-volume deep dive on number sieves: the oldest algorithm in number theory, and the strange family of machines built to run it faster than any human could. It explains what a sieve is, works the simplest example by hand, introduces the one idea that makes sieving mechanical — that a modulus is a loop — and then tours the whole story in miniature, from a Greek librarian’s method for finding primes, through a Frenchman’s hand-cranked “congruence machine,” a Berkeley undergraduate’s frame of bicycle chains and a photoelectric stack of gears, to the electronic sieves of the late twentieth century and the number field sieve that factored a 260-digit RSA key in September 2026.

The volume assumes nothing beyond school arithmetic. Readers who want the mathematics in full can go straight to Volume 2 (primes and Eratosthenes) and Volume 4 (congruences); readers who want the machines can jump to Volumes 5–8. The series ends on a workbench: three volumes of build procedures for a faithful bicycle-chain sieve, a faithful photoelectric gear sieve, and a small electronic sieve built from thirty microcontrollers, followed by a volume that puts all three to work on problems the Lehmers solved.

1.1.1 The Fourteen-Volume Series

Table 1 — The Fourteen-Volume Series

Vol	Title	Focus
1	Number Sieves — Machines That Throw Numbers Away (this volume)	Orientation: what a sieve is, the loop idea, the whole story in miniature
2	Prime Numbers and the Sieve of Eratosthenes	Primes, Euclid, Eratosthenes and Nicomachus, the sieve by hand, π(x), gaps, twins, Mersenne primes
3	Beyond Eratosthenes — Wheels, Segments and Sieve Theory	Wheels, segmented sieves, Sundaram, Atkin, Legendre, Brun, Selberg, the large sieve, sieves in code
4	Congruences Made Mechanical	Clock arithmetic, quadratic residues, the Chinese Remainder Theorem, Fermat’s method, N = 7663 worked in full
5	Before the Machines — Carissan, Gérardin, Kraitchik and the Lehmers	The French sieve-builders and the Berkeley family of number theorists
6	The Bicycle-Chain Sieve (1926–1928)	Chains, pins and contacts: Lehmer’s first machine
7	The Photoelectric Gear Sieve (1932)	Gears with holes, a light beam and a photocell
8	Electronic Sieves, 1965–2001 — and a Tiny Sieve in ATtinys	Delay lines, shift registers, VLSI, and kbsriram’s ATtiny412 board
9	What a Sieve Can Solve — Worked Problems from Easy to Hard	Factoring, primality, Diophantine problems, pseudosquares
10	Sieves in Cryptography — From Lehmer to the Number Field Sieve	Quadratic sieve, number field sieve, TWINKLE and TWIRL, RSA
11	⭐ Building the Bicycle-Chain Sieve	Roller chains, sprockets, microswitches: a faithful mechanical build
12	⭐ Building the Photoelectric Gear Sieve	Machined or printed gears, a light beam and a photodetector
13	⭐ Building the Tiny Sieve (ATtiny412 + RP2040)	The open electronic sieve, assembled and programmed
14	Running Lehmer’s Problems — Test Protocol and Results	Putting the three machines to work and comparing them

---

1.2 A Machine Whose Job Is to Say No

Most machines that compute are built to produce an answer. An adding machine adds; a calculator multiplies; a computer runs a program and prints a result. A sieve does something stranger. It is handed an enormous supply of candidates — every whole number in some range, say — and its whole job is to throw away the ones that fail. It never computes the answer directly. It simply rejects, and rejects, and rejects, until what is left over can only be the answer.

The kitchen image is exact. Pour flour through a sieve and the lumps stay behind. Pour numbers through a number sieve and the ones that fail a test fall out. Stack several sieves, each with a different mesh, and only the numbers that pass every test come out the bottom. That is the whole definition:

A number sieve keeps the candidates that survive every test, and discards the rest.

What makes the idea powerful is that each individual test can be very weak. “Is this number odd?” rejects only half the candidates. “Does it leave a remainder of 1 or 4 when divided by 5?” rejects three-fifths. Neither test alone comes close to finding anything. But the tests are independent, and independent filters multiply. Twenty tests that each let through about half the candidates let through about one candidate in a million. Thirty such tests pass about one in a billion. A sieve is a machine for turning a large number of feeble, cheap tests into one very strong one.

That trade — many cheap tests instead of one expensive one — is why sieves are still at the heart of serious number theory more than two thousand years after the first one was described, and why the record-setting factorisations of RSA cryptographic keys, including the 260-digit one broken in September 2026, spend most of their running time in a step that is literally called sieving.

1.3 The Simplest Sieve, by Hand

The oldest sieve, and the one that gives the whole family its name, finds prime numbers. A prime is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13 and so on. The method is credited to Eratosthenes of Cyrene, a third-century-BC scholar who ran the great library at Alexandria, and is recorded about three centuries later by Nicomachus of Gerasa in his Introduction to Arithmetic, which calls it a koskinon — a sieve (Wikipedia, “Sieve of Eratosthenes”). Volume 2 tells that story and works the method in detail. The short version takes a pencil and two minutes.

Write down the numbers from 2 to 61. The first number, 2, is prime; keep it and strike out every second number after it — 4, 6, 8 and so on. The next number not struck is 3; keep it and strike every third number. Then 5, then 7. After the pass for 7, stop. Every number still standing is prime.

Two features of this tiny exercise carry through the entire series.

First, no number is ever tested for primality. Nobody asks “is 59 prime?” and divides it by everything smaller. The sieve simply marches through the list in strides, crossing out, and the primes are whatever the strides never land on. Marching in strides is cheap — it is just counting — which is why a sieve can process a range of numbers far faster than testing each number one at a time.

Second, it is enough to stop early. Every composite number below 64 = 8 × 8 has a prime factor no bigger than 7, so once the multiples of 2, 3, 5 and 7 are gone, nothing composite can remain. Volume 2 explains why the stopping point is always the square root of the top of the list.

1.3.1 A sieve that is not about primes

The same procedure works for any question whose answer can be phrased as a list of conditions. A famous example comes from the Chinese Sunzi Suanjing, a mathematical manual of roughly the fifth century AD (Wikipedia, “Chinese remainder theorem”): there is a number of things, unknown; counted in threes, two are left over; counted in fives, three are left over; counted in sevens, two are left over. How many things are there?

A sieve solves it without any algebra. List the candidates 0 to 104. Keep only those that leave remainder 2 when divided by 3: 2, 5, 8, 11, 14, 17, 20, 23, 26 … Of those, keep only the ones that leave remainder 3 when divided by 5: 8, 23, 38, 53, 68, 83, 98. Of those, keep only the ones that leave remainder 2 when divided by 7. Exactly one survives: 23. The three tests are each weak — the first keeps a third of the numbers, the second a fifth of what is left, the third a seventh — but together they leave a single number in 105.

That is already the essential shape of every problem the Lehmers’ machines attacked. The candidates are whole numbers. The tests are statements about remainders. And the answer is whatever survives them all.

1.4 The Big Idea: A Modulus Is a Loop

The remainder a number leaves on division by m is called its residue modulo m, and m is called the modulus. Residues are what make sieving mechanical, for one simple reason: as the candidates count upward 0, 1, 2, 3, …, the residue modulo 5 goes 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, … forever. It cycles. And anything that cycles can be built as a loop.

Take a loop with exactly 5 positions — a ring of 5 links of bicycle chain, a gear with 5 teeth, a strip of film 5 frames long joined end to end. Number the positions 0 to 4. Advance the loop one position for every candidate. After the loop has been advanced b times, the position under a fixed pointer is exactly b mod 5. The loop does not calculate a remainder; it is the remainder.

Now mark the positions that pass the test. If the condition is “the remainder modulo 5 must be 1 or 4,” fix a small tab to positions 1 and 4. Mount a switch above the loop so that it closes only when a tab passes under it. Do the same with a loop of 7 positions for the modulo-7 test, a loop of 3 for the modulo-3 test, and so on — as many loops as there are tests — all driven together from one shaft, so that every loop advances one position per candidate. Wire the switches in series. (Lehmer’s own 1928 machine used the mirror-image arrangement, which works the same way: a normally closed spring contact on each chain, all in parallel, so the circuit broke only when every chain lifted its spring at once. Volume 6 has the details.)

The circuit completes only at a step where every loop presents a tab at the same time — that is, at a candidate b whose residue passes every test simultaneously. At that instant the machine stops, and the counter on the drive shaft shows the number of steps taken: the candidate that survived. Everything else, the millions of candidates that failed at least one test, has rushed past without anyone writing anything down.

That is the whole machine. Derrick Henry Lehmer built it in 1926 from bicycle chains in the student workshop at the University of California, Berkeley, with chains whose numbers of links matched the primes up to 67 (IEEE Computer Society, “Derrick Henry Lehmer”). There are exactly nineteen primes up to 67, and if each loop lets through about half the residues, nineteen loops in series let through roughly one candidate in 2¹⁹ ≈ 524,000. Volume 4 shows why a well-chosen modulus does reject about half, and why loops whose lengths share no common factor behave like independent filters.

1.4.1 Why parallel loops beat a fast clerk

A human working this kind of problem by hand — or a 1920s desk calculator — tests one condition at a time: divide, check the remainder, move on. A loop machine tests all of its conditions at once, on every step, because every loop is turning simultaneously and every switch is reporting simultaneously. The only arithmetic performed is the act of advancing a chain by one link. Lehmer himself later put the point with relish when describing how the ENIAC, the first general-purpose electronic computer, was pressed into service as a sieve in 1946: “This was a highly parallel machine, before von Neumann spoiled it” (IEEE Computer Society). A sieve is the purest example of parallel computing — dozens of independent units all doing the same trivial thing at once, with a single AND gate at the end.

1.5 Two Things Sieves Are Good For

Almost every sieve in this series does one of two jobs.

Finding numbers with a property. The Sieve of Eratosthenes finds primes. Other sieves find twin primes, or numbers that can be written as a sum of two squares, or numbers whose residues follow a prescribed pattern. Volume 3 shows how mathematicians turned the procedure into sieve theory — the art of estimating how many survivors a sieve leaves without actually running it — and used it to prove deep facts about the primes.

Factoring a number. This is where the machines come in. To factor an odd number N, Pierre de Fermat observed in the seventeenth century that it is enough to write N as a difference of two squares: if N = a² − b², then N = (a − b)(a + b), and the two brackets are factors. Searching for such an a and b is slow if done blindly. But a perfect square can only leave certain remainders — a square divided by 5, for instance, always leaves 0, 1 or 4 — so most candidates can be thrown out by looking at residues alone. Each modulus becomes a loop; each loop carries tabs on the residues that could still give a square; and the machine stops on the candidates that survive them all. Volume 4 does this with N = 7663, which falls apart as 79 × 97 on the ninth step.

Primality proofs, solutions of Diophantine equations and searches for “pseudosquares” are variations on the same theme. Volume 9 works through a graded collection of them, from puzzles a sieve on paper can handle to problems that kept the Lehmers’ machines busy for days.

1.6 A Quick Tour: Two Thousand Years of Throwing Numbers Away

1.6.1 Alexandria and after

The Sieve of Eratosthenes was described for more than a thousand years in commentaries and manuscripts on Nicomachus; one modern survey of Greek manuscripts found forty-four drawn sieves in thirty-five manuscripts, many of them carrying the heading Eratosthenes’ sieve (searching greek manuscripts for sieves). It remained the standard way to make tables of primes into the twentieth century: the elder Lehmer, Derrick Norman Lehmer, published a list of every prime up to 10,006,721 in 1914, a companion to his 1909 factor table of the first ten million numbers — tables produced, in the end, by organised crossing-out. Volumes 2 and 3 cover the sieve, its modern variants and the theory it grew into.

1.6.2 Fermat, Gauss and the residue idea

Two later ideas turned the sieve into a tool for factoring. Fermat’s difference-of-squares method, described in a 1643 letter in which he split 2,027,651,281 into 44,021 × 46,061 (PrimePages, “2027651281”), supplied the target. Carl Friedrich Gauss’s Disquisitiones Arithmeticae of 1801 supplied the language — congruences and residues — and, in its articles 319 onward, a “method of exclusion” for ruling out candidates by their residues modulo a series of small numbers (Wikisource translation). Exclusion by residues is precisely what a loop with tabs does. Volume 4 develops both.

1.6.3 The first machines

The idea of mechanising exclusion appeared within a few years of the twentieth century. F. W. Lawrence outlined an electromechanical sieve in 1896, and in Paris around 1912 André Gérardin, Maurice Kraitchik and the Carissan brothers all proposed or built prototypes (Wikipedia, “Lehmer sieve”). The one that worked was Eugène-Olivier Carissan’s machine à congruences, a hand-cranked device of concentric rings completed around 1919 after delays caused by the First World War. It vanished from view after his death, sat in a drawer at the Observatoire de Bordeaux for about fifty years, and was rediscovered and described by Jeffrey Shallit, Hugh Williams and François Morain in 1995; it is now in the collections of the Conservatoire National des Arts et Métiers in Paris (Shallit, Williams & Morain, “Discovery of a Lost Factoring Machine”). Volume 5 tells the French story.

1.6.4 The bicycle-chain sieve

In 1926 Derrick Henry Lehmer — “Dick,” son of D. N. Lehmer — built his first sieve at Berkeley from looped bicycle chains on a common shaft. Long screws or rods fitted in place of chain pins at the acceptable residues acted as the tabs, and a projecting pin lifted a small tungsten-tipped spring off a brass bar above each chain. While any spring stayed down, current flowed; when every spring was lifted at once, the circuit broke, a relay dropped out and the motor stopped (Lehmer 1928). Lehmer’s chain sieve factored numbers that had defeated hand computation, and its design was refined and written up over the next two years. The original machine is lost. A reproduction made in 1981 by Robert Canepa with Lehmer — a sawhorse-shaped wooden frame carrying the chains on sprockets, a microswitch above each chain and a mechanical revolution counter — is in the Computer History Museum (CHM catalogue 102647620). Volume 6 is devoted to the chain sieve, and Volume 11 to building one.

1.6.5 The photoelectric gear sieve

Chains are slow; they stretch, and the contacts bounce. In 1932 Lehmer replaced them with a stack of gears, one for each modulus, each drilled with a hole at every acceptable residue and all driven from a common gear. A beam of light was aimed through the stack. Only when the holes in every gear lined up at once could light reach a photocell on the far side, and its pulse, amplified, stopped the machine. It examined about 5,000 candidates a second (IEEE Computer Society) and was later shown to the public at Chicago’s Century of Progress exposition. The machine survives at the Computer History Museum, catalogued as the “Photoelectric Number Sieve Machine (‘Gear Machine’)”, 1932, weight 275 pounds (CHM catalogue X85.82). Lehmer described it in “A photo-electric number sieve,” American Mathematical Monthly 40 (1933). Volume 7 covers the gear sieve and Volume 12 the procedure for building one.

A third Lehmer machine of 1936 replaced the gears with loops of 16 mm movie film punched with holes, read by brushes making electrical contact through the holes (Wikipedia, “Lehmer sieve”).

1.6.6 Electronic sieves

After the Second World War the loops went electronic. Lehmer and his wife Emma — herself a number theorist, who had been a student of his father — ran a sieve on the ENIAC in 1946. In the mid-1960s Lehmer built the Delay Line Sieve DLS-127, in which each modulus was a loop of electrical delay line: a pulse circulating around a line of the right length returned to its start every m clock ticks, just as a chain returns to its start every m links (Wikipedia, “Lehmer sieve”). It ran around the clock for about a decade. Later sieves used shift registers and finally custom integrated circuits; Richard Lukes’s 1995 thesis at the University of Manitoba describes a VLSI sieve running at billions of candidates per second. Daniel J. Bernstein’s 2001 method of generating the survivors directly, rather than filtering for them, made such special-purpose hardware largely unnecessary (kbsriram, A Tiny Sieve). Volume 8 covers this generation, and ends with a modern homage: kbsriram’s Tiny Sieve, a board that re-creates a Lehmer-style electronic sieve with thirty ATtiny412 microcontrollers, one per modulus, published with open schematics and firmware (github.com/kbsriram/a-tiny-sieve).

1.6.7 The sieves that break codes

The most consequential sieves of all never involved a chain or a gear. Early in 1981 Carl Pomerance realised that “something akin to the sieve of Eratosthenes” could quickly pick out, from a long run of values of the polynomial Q(x) = x² − n, the ones that factor completely into small primes — the raw material of Maurice Kraitchik’s 1920s refinement of Fermat’s method (Pomerance, “A Tale of Two Sieves,” Notices of the AMS, 1996). The trick is the same one the loop machines use: for each small prime p, the values of x at which p divides Q(x) recur at fixed residues modulo p, so the sieve can stride through them without ever dividing. The result, the quadratic sieve, factored the 129-digit challenge number RSA-129 in April 1994 in a distributed computation led by Derek Atkins, Michael Graff, Arjen Lenstra and Paul Leyland. John Pollard’s number field sieve, circulated in 1988 and generalised over the following years, overtook it in 1996.

Sieving is still the dominant cost. The 829-bit RSA-250 was factored with the number field sieve in February 2020 by Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann; on 3 September 2026 Eric Lu of Cognition factored the 862-bit RSA-260 with a GPU implementation of the general number field sieve, of which roughly 3,800 of the 4,900 GPU-days went to the lattice-sieving step (Wikipedia, “RSA Factoring Challenge”; Cognition, “Factoring RSA-260”). Volume 10 explains how a sieve sits inside these algorithms, and why proposals for dedicated factoring hardware — Adi Shamir’s optoelectronic TWINKLE (1999) and Shamir and Eran Tromer’s TWIRL (2003) — look so much like Lehmer’s machines.

1.7 Why Build One Now?

A desktop computer running a well-written sieve outpaces any mechanical sieve by many orders of magnitude, so the reason to build the old machines is not speed. It is that a sieve is the rare computing machine whose entire operation can be seen. On a chain sieve every modulus is a visible loop, every acceptable residue is a pin that can be touched, and the moment of success is a physical event — a set of switches clicking closed together, a motor stopping. On a gear sieve the answer is literally a beam of light that gets through. Watching one run teaches modular arithmetic and the Chinese Remainder Theorem more directly than any textbook can.

The machines are also within reach of a home workshop. Roller chain, sprockets and microswitches are catalogue items; gears can be cut, machined or 3D-printed; and the electronic version is a single circuit board. kbsriram’s Tiny Sieve project, which prompted this series, shows that even Lehmer’s later electronic design can be rebuilt at small scale with modern parts, and its results table — the speed of each historical machine against the new board — gives the builds a yardstick to measure against.

1.8 The Three Builds

The series closes with four practical volumes.

• Volume 11 — the bicycle-chain sieve. A faithful mechanical build: real roller chains on sprockets sharing a common shaft, pins or extended rivets at the acceptable residues, a contact over each chain wired so the circuit changes state only when every chain agrees, a motor, and a counter. The volume covers choosing the moduli, cutting each chain to an exact number of links, setting the pins for a given problem, and stopping the drive cleanly when the circuit opens — Lehmer’s own break-to-stop arrangement, normally closed contacts in parallel.
• Volume 12 — the photoelectric gear sieve. Gears with tooth counts equal to the moduli, each drilled (or printed) with holes at the acceptable residues, all meshed to a common drive, with a light source on one side of the stack and a photodetector on the other, as in Lehmer’s 1932 machine.
• Volume 13 — the Tiny Sieve. The electronic sieve from kbsriram’s open design: thirty ATtiny412 microcontrollers, one per modulus, coordinated by an RP2040.
• Volume 14 — running Lehmer’s problems. A test protocol for all three machines, using factorisation and quadratic-residue problems of the kind the Lehmers ran, with a log of results and speeds.

1.9 How to Read This Series

The volumes are written to be read in order, but each can stand on its own.

• For the mathematics, read Volumes 2, 3 and 4. They need nothing beyond arithmetic and patience, and every worked example in them can be checked with a pencil.
• For the history of the machines, read Volumes 5 to 8. They draw on the Lehmers’ own papers, the Computer History Museum’s collection, and the 1995 rediscovery of Carissan’s machine.
• For applications, read Volumes 9 and 10, which move from puzzles to the factoring of cryptographic keys.
• For the builds, read Volume 4 first — the builds make sense only once a loop with tabs reads as a modulus with its acceptable residues — and then Volumes 11 to 14.

1.10 The One-Paragraph Version

A number sieve finds the numbers that pass a list of tests by throwing away every number that fails any one of them. The tests are usually about remainders, and because remainders repeat in cycles, each test can be built as a loop — a chain of m links, a gear of m teeth, a delay line m ticks long — with markers on the acceptable positions. Turn all the loops together and the machine stops only where every loop shows a marker at once. Eratosthenes’ sieve did this with a pencil to find primes; Carissan, and then D. H. Lehmer with bicycle chains and photoelectric gears, did it with machinery to factor numbers and solve equations; electronic sieves did it with delay lines and chips; and the quadratic and number field sieves, which factor RSA keys, still spend most of their time doing a version of it today. The remaining thirteen volumes are the long version.

---

Next — Volume 2: Prime Numbers and the Sieve of Eratosthenes. The oldest sieve of all, done properly: what a prime is, why there are infinitely many of them, who Eratosthenes was and how his method reached us through Nicomachus, why the crossing-out starts at p² and stops at √N — and what the sieve reveals about how the primes thin out, cluster and pair up as the numbers grow.