
Got these three ATtiny412s and a Pico to factor 5,283,065,753,709,209 - the number D.H. Lehmer's gear machine factored in 1932.
The sieve scanned 5.6 million candidates in 113 seconds and rejected 87% of them. The Pico spent 23 minutes testing the 740,000 that survived. The sieve is idle for 92% of the run, waiting for the Pico to check survivors.
So a sieve which scans ten times faster than Lehmer's 1932 gear machine, takes about as long to factor the same number. The difference is the number of moduli. The three moduli let through around one in eight candidates. Lehmer's thirty let through so few that a human could hand-check the survivors without adding much more time to the process.
Where the candidates come from
The first build log showed how to sieve y^2 - 2x^2 = 4001. Factoring is the same kind of problem - find whole numbers that satisfy a quadratic equation.
Take any odd number N = p*q. Both factors are odd, so their sum and difference are even, and a = (p+q)/2 and b = (p-q)/2 are whole numbers. Then N = a^2 - b^2. So find a and b, and the factors are a+b and a-b. So factoring can be expressed as a quadratic equation to solve in whole numbers.
To sieve it, a starts just above sqrt(N) - about 72 million for our 16-digit number - and climbs. Our two factors turn out to be very far apart, 59,957 and 88 billion, so a reaches a solution after 44 billion. At the gear machine's 5,000 candidates a second that would be 102 days of continuous running.
Lehmer did an additional reduction in number theory first. He showed the number must be of the form a^2 + 7b^2, and that a second solution c^2 + 7d^2 gives a factor directly as gcd(N, ad + bc). He also showed b must be a multiple of 4, so we actually solve for a^2 + 7*(4*k)^2 = N
That leaves about 6 million candidates to check with the sieving machine.
Here's what our console log from the RP2040 shows - we stop at the second solution for our equation after 1,471 seconds and scanning 5,676,028 numbers.
...
>>> FOUND REPRESENTATION: M = 66855539^2 + 7 * 10779628^2 (k = 2694907, 706.32s) <<<
...
>>> FOUND REPRESENTATION: M = 40923451^2 + 7 * 22704112^2 (k = 5676028, 1471.69s) <<<
============================================================
FACTORIZATION COMPLETE in 1471.69s!
Factors of 5283065753709209:
Factor 1: 59957
Factor 2: 88114244437
Verification: 59957 * 88114244437 == 5283065753709209 (True)
============================================================
Every sieve has something slower behind it
A sieve only rejects candidates. Whatever survives has to be checked by something else, and that something else is always slower (or the sieve wouldn't be useful.)
In 1928 the Lehmers built a sieve from 19 bicycle chains on a common shaft, one chain per modulus, with a twist of chickenwire at each accepted link tripping a microswitch, and a revolution counter for the current number. The switches were wired in series, so a candidate nobody rejected completed the circuit and stopped the motor. Then a person checked if the candidate was a solution.
A 1932 machine built with gears replaced chains with steel gears and the switches with a beam of light through aligned holes. A photoelectric cell would detect when all holes lined up and stop the motor.


Every number sieve ever built has the same two stages: a fast rejecter and a slower checker. New technology simply changed what each stage was made of, allowing larger and larger problems to be solved: from 60 candidates a second in 1928 to 6.4 billion in 1995, through bicycle chains, steel gears, surplus Navy delay lines and finally custom VLSI.
| Machine type | year | moduli | candidates/sec | who checks survivors |
|---|---|---|---|---|
| bicycle chains | 1928 | 19 | 60 | human |
| 16mm film | ~1930 | 18 | 60 | human |
| steel gears | 1932 | 30 | 5,000 | human |
| delay lines | 1965 | 36 | 1,000,000 | printer, CDC 6400 |
| shift registers (Winnipeg) | ~1980 | 32 | 132,000,000 | host minicomputer |
| ROM + counter (Berkeley) | 1982 | -- | 16,600,000 | host computer |
| VLSI (MSSU) | 1995 | 30 | 6,400,000,000 | host computer |
By 1982 all sieving machines were built as a special purpose device built to reject as fast as possible, and a general-purpose computer that loaded the patterns, drove the clock, and tested the survivors. My build is that architecture as well.
What ended the sieve machines was better algorithms, not faster hardware. Sieving stopped being the fastest way to factor around 1970, but the machines were used through the 1990s on other number-theory searches. A sieve is fast because rejecting is cheap, but it still steps through every integer in the range. In 2001 D. J. Bernstein demonstrated a method that takes the same moduli and generates the survivors directly, ending the need for specialized number sieving machines.
Three chips and a Pico
My design is based on a sieving machine D.H. Lehmer described during this 1982 lecture. It's a great watch if you're into oddball contraptions to solve deep number theory problems.
In the 1982 version, each gear becomes a bit pattern in ROM with a counter indexing it. I'll call this repeating pattern a ring. The beam of light becomes a shared line driven by the ROM values, and the revolution counter is within a general purpose computer that sets up the moduli, drives the device and checks survivors for solutions.
I use an ATtiny412 for each ROM/counter per modulus, and an RP2040 as that computer.

Each ATtiny is initialized over I2C with its ring - a circular bit-array of accept/reject bits (the first build log's row of yes/no values). The ring is saved in RAM, so it can be initialized to any modulus. The 412 has 2048 bits (256 bytes) of RAM available, but I limited the moduli to be 128 or less for now. This also allows loading arbitrary moduli, unlike sieve machines that have a hard-coded set of moduli in their design.
Lehmer called these 'adjustable sieves" - useful for problems where you had to choose the moduli carefully to get useful sieving. In my case, I can also use it to replicate the various historical machines to get a realistic sense for how they worked, which should be fun.
All tinys share one open-drain line, VOTE. They release it to accept, or pull it low to reject. A survivor is found if this line stays high. An open-drain line keeps the wiring simple, though the scanning speed is limited by the RC constant on it. Running in the high MHz would likely need a wide AND gate with the tinys actively driving the line.
The tinys are clocked with a common REQ line so they can drive the VOTE line in lockstep as they increment their ring counters. They have to start together as well. A ring one position off votes against the wrong number, and silently corrupts all results.
The Pico first holds REQ low and initializes the rings over I2C, sending each ATtiny its modulus and ROM bit pattern, and resetting its counter to zero.
Once initialized, on the rising edge of REQ every ATtiny drives VOTE from its current bit and advances its ring counter, wrapping at its modulus. The candidate number never reaches the ATtinys - they only ever advance their ring counter and read a bit.
The Pico samples VOTE after the falling edge. If VOTE is still high, no chip rejected, and the Pico computes M - 7(4k)^2 and tests whether it is a perfect square.
The Pico drives REQ, monitors VOTE and updates a 64-bit counter all in PIO. It pushes candidates over a FIFO, which the main CPU then checks. This was my first time really getting into PIO and I was surprised at how much functionality you can squeeze out of it.
The firmware and pico code including the setup to factorize our 16-digit number is all available in GitHub here.
Things I also measured
First, I pre-calculated survivors for the first 10,000 candidates and compared it with what the sieve produces.
--- Mode A: Lint & Verification (first 10000 candidates) ---
Expecting 1305 survivors (13.05% pass rate)...
PASS: 100% agreement over 10000 candidates (199.9 ms, 50.04 kHz).
The three ATtinys agreed with the pre-calculated list on each of the first 10,000 candidates, so the VOTE logic seems to be working.
Moduli 5, 11 and 23 accept 3/5, 5/11 and 11/23 of candidates, predicting 13.043% survival. Over the full run it measured 13.044% and that checks out too.
I also took some scope traces on the REQ (blue trace) and VOTE (yellow trace)

When REQ rises, VOTE is pulled low after about 5us. That 5 us is the ATtiny (around 100 cycles at 20Mhz) to handle the interrupt, read one bit, advance the counter, drive the pin. Currently the tinys set a flag on a rising interrupt on that pin, and a main loop waks up to drive the VOTE line. If needed, I could roll this into the interrupt handler and do it quicker.
The VOTE open-drain line releasing on a candidate shows an RC curve than an edge, taking around 10.1us to reach the supply.

The code currently just uses the internal pullup on the Pico - around 50-60kOhm. The RC constant is around 2us, so we might have around 35pF on the line between the breadboard and the probe.
A candidate therefore takes 5 us of attiny compute and 10 us of RC, so I clock REQ every 20 us, 50KHz.
A smaller resistor pulling up the line should bring the RC constant down, and we could optimize the ATtiny code as well. So, I think there's some headroom to increase the scanning speed if needed.
Checking a survivor however is an order of magnitude more expensive - that takes around 1.85 ms on the Pico, or about 92 REQ periods.

This is what it looks like on the scope. A short burst of REQ pulses picks up a new survivor, then a long flat stretch with VOTE high and no clock at all. The sieve is waiting here for the Pico to finish square root calculations.
A sieve machine in this state is said to be "filter bound" - the survivor rate overwhelms whatever is checking survivors, so the machine runs far below the rate the sieving device can sustain.
The fix is more moduli.
Each added coprime modulus rejects about half of what is left, so for instance twelve moduli would leave around 1,100 survivors instead of 740,000. Checking time with 12 moduli should drop from 23 minutes to 2 seconds, and the run would be dominated by the roughly 2 minutes of scanning at 50KHz.
kbsriram
Discussions
Become a Hackaday.io Member
Create an account to leave a comment. Already have an account? Log In.