Project Logs

Collapse

The modulus chorus plays for us

kbsriram • 09/21/2026 at 00:55 • 0 comments

Back on the breadboard, I'd factored 5,283,065,753,709,209 with three ATtiny moduli. It took 25 minutes, about as long as Lehmer's 1932 gear machine, even though the breadboard sieve can run ten times faster. Having only three moduli let through 740,000 survivors, which the Pico has to check. This left the sieve idle over 90% of the time waiting on the Pico.

With 30 moduli the same problem now finishes in under two minutes, about ten times faster than the gear machine, as expected. Only two candidates survive, and both are real solutions. Two of Lehmer's gears accept every value on this problem and do no filtering at all, so those two cards stay dark for the whole run. He couldn't swap in different moduli because they were fixed by the gears he had, but the remaining 28 still filtered enough. My current sieve is also ten times faster than the breadboard version, so at its full rate of 500,000 numbers per second the same run takes 11 seconds.

With the machine now fully working, over several hours I ran published problems from three of Lehmer's sieves. The 1928 bicycle chain machine, the 1932 gear machine, and the 1965 delay line electronic sieve.

1928 and 1932: bicycle chains and gears

In 1928, Lehmer published [LF28] with results from the bicycle chain machine, and [PS33] and [NF33] in 1933 with results from the gear machine. Each result gives how fast the machine ran, where it stopped, and how long that took.

I set my REQ clock, the shared line that steps every card, to each machine's own rate. That is 50 numbers/sec for the bicycle chain machine, and 5,000/sec for the gear machine. The chain machine had 19 chains, so those runs use 19 cards. The gear machine had 30 gears, so those use all 30.

Problem	Paper	Rate	Published notes	My sieve	Stops
9,999,000,099,990,001	LF28	50/s	"about 2 hours"	2 h 14 min 09 s	2
a factor of 3^111 + 1	LF28	50/s	"only 4 seconds"	2.96s	1
4,500,383,424,373 as a sum of two squares, run1	LF28	50/s	"one stop, not a solution"	1 h 05 min 42 s	1
same problem, run2	LF28	50/s	"stopped only once"	52 min 37 s	2
2^79 - 1	PS33	5,000/s	"12 s"	11.31 s	1
2^93 + 1	NF33	5,000/s	"a few seconds"	1.41 s	1

Every solution matched the published one as expected. Run 1 of the sum of two squares has no solution in its range, so it ran to the end. My measured times agree as well. My sieving rate comes out about 0.5% below the REQ clock rate, from the periodic self-test checkpoints and OLED updates.

Interestingly, I found some minor discrepancies from the published results.

The 1928 paper does not note two of the stops

The bicycle chain machine [LF28] stops when a survivor is found, and a person then checks it by hand. The paper says how many times that happened. On two of the four runs, my sieve stopped one more time than was noted in the paper.

Sum of two squares, run 2. Paper: "stopped only once", at x = 157,044. Mine stopped first at x = 102,151, a = 510,758, N minus a^2 = 4,239,509,689,809, not a square, 18 minutes earlier.
N = 9,999,000,099,990,001. Paper: "stopped at x = 400,453". Mine first stopped at x = 257,749, a = 1,955,793,401, a^2 minus N = 3,815,128,827,295,156,800, not a square, 48 minutes earlier.

Neither could have been rejected by that machine. Both are quadratic residues of every prime up to 67, its largest chain, and the smallest prime that rejects them is 73. So the machine would have stopped. I'm assuming these were just left out of the final write-up.

Two smaller items

[PS33] gives the wrong period for the gear machine (the number of steps before the initial gear positions repeat) as 2497194316592991015263471297031949336968700272210.

That number is actually the product of the first 30 primes, with 79 multiplied in twice
The first 4 gears actually have prime power tooth counts, 64, 27, 25, 49. (The rest were the remaining primes 11 to 113)
These are all coprime, so the true period is the product of the gear teeth counts 318629350775409486504503679418760117932208844859200. That's about...

The modulus chorus rehearses
kbsriram • 09/15/2026 at 18:21 • 0 comments

Here is a self-test running across all thirty cards on a stripboard backplane. Each LED lights in slot order while the OLED reports the address it is checking.

Last time, I tested the cards one at a time. They now sit in a stripboard backplane with 30 headers, which brings its own failures. A cold joint or a bridge on the backplane, or a card not seated far enough into its header. A card that incorrectly holds the shared VOTE line low rejects candidates that should pass. This causes the run to silently fail, as every valid solution is discarded before verification by the Pico. The machine now checks itself before it starts. I also wanted to know how fast it can run, so I measured two things on VOTE with all 30 cards fitted: how long after a REQ edge a card pulls the line low, and how long the line takes to return high once every card has released it.

The stripboard backplane

I built it on a 3U Eurocard stripboard, with 62 holes along each of 38 copper strips.

Fitting thirty 8-pin daughter cards, a Pico and an OLED is tight. I tried several layouts in diylc before settling on three rows of ten, with the Pico on the left and the OLED in the corner beside it. The Pico's right-hand column of pins lands on the same strips as the first card slot, so ground, SDA, SCL, VOTE and REQ reach it directly. Vcc is taken off a jumper from the 3V3 pin on the Pico.

An ATtiny412 draws 2.7 mA running at 10 MHz, and each LED about 1 mA, so thirty cards with every LED lit come to roughly 111 mA. The OLED takes an additional 20 mA or so. The Pico's regulator is rated at 800 mA, so the 131 mA total leaves plenty of margin.

The strips are on the underside, so everything is mirrored once the board is turned over to work on them. I drew the component outlines on the top side first, and poked a wire through each hole to confirm a position before cutting anything.

To break a strip I spot-face a hole. I place a drill bit at a hole and gently turn it by hand until the ring of copper around it is gone, then verify that the two sides of the break are no longer connected. Stripboard has no solder mask, so solder spreads about one hole's width along the strip from every joint. If you solder first, cutting through it can be difficult. So I made the breaks first, then the jumpers while nothing tall got in the way, and the headers last.

Flashing thirty cards

Each card gets its own I2C address as a compile-time define, so a batch script walks through all thirty, one at a time. It rebuilds the binary for each address and prints which slot the card goes into. Slotting them sequentially along the rows makes it easier to tie an I2C address to a physical position when something goes wrong later.

After the shipping image is flashed, the jig talks to the card over I2C: it reads STATUS back, loads a modulus-7 ring, steps 14 REQ edges by hand, and checks VOTE against the pattern that ring should produce. I couldn't do this in the last build as there was no I2C firmware to talk to yet.

A failure doesn't advance the address counter, so I can reseat the card and retry. Poor seating in the jig socket was the only failure I saw during flashing.

Self-checks

With one open-drain VOTE line driven by 30 cards and no error detection, a single mistake can silently make a run worthless. A card stuck holding VOTE low rejects valid candidates, and the run then completes and claims no solutions exist.

I first enhanced the I2C protocol, to make it more robust and to let me inspect each card's internals. I added a CRC-8 checksum, and each command always returns a single-byte response code. So a card can reject a corrupted command and inform the Pico, rather than silently doing something unexpected. I added a STATUS command to return the card's ring position, whether it is armed, its modulus, firmware version and why it was last reset. The reset reason shows whether a card was reset by a brownout part-way through a run.

I then wrote a set of...
Read more »
Qualify the moduli
kbsriram • 09/12/2026 at 00:44 • 0 comments
The boards are here, and they are smol!

Soldering headers across 30 cards is 240 joints, and any one could break the sieve silently. An open joint only costs time. More candidates survive, and the Pico has to check each one. A bridge to ground on VOTE is worse. The card will reject candidates that should pass, and the run ends without a solution.

On a shared bus, any of the thirty could be the culprit. I have to flash each card individually anyway, so I can also test each in isolation before flashing it.

Soldering headers

Soldering a right angle header on a small board like this can be tricky to keep the pcb aligned with the pins. I used a sacrificial female header under the ground side of the pcb, which is component free and flat. I inserted the right angle pins in another female header, which keeps the pcb in the same plane as the pins, and then solder the headers.

The test jig

The jig is just a small stripboard with two 8-pin male headers to secure it to a breadboard and a female header for the card under test. A Pico to test for open/shorts and a UPDI Friend to flash the code stay on the breadboard. The cards are never inserted or removed from the breadboard directly, avoiding damage over 30 cards.

The test software

I first flash test code that just leaves the four bus lines in high-Z with pullups, and blinks the LED as a visual check it works. The Pico drives each line low in turn and checks the others are still high. This find bridges between lines. It then releases everything and checks all lines are high. The pullups are in the tiny, so any open connection would stay low.

Here's a successful run.
```
==================================================
 Stage 2: Running electrical self-test via Pico
==================================================
Local directory . is mounted at /remote

==================================================
 ATtiny412 Flash-Time Self-Test Jig
==================================================
[1/4] Check 1: Shorts to GND ... [PASS]
[2/4] Check 2: Pin Bridges & VCC Shorts ... [PASS]
[3/4] Check 3: Open Circuits ... [PASS]
[4/4] Check 4: JP1 & PA7 Isolation (3.0s) ... [PASS]

==================================================
RESULT: ALL CHECKS PASSED.
Card is verified. Ready for final shipping image.
==================================================
```
Here's one with a failure, indicating a bridge between two pins.
```
==================================================
 Stage 2: Running electrical self-test via Pico
==================================================
Local directory . is mounted at /remote

==================================================
 ATtiny412 Flash-Time Self-Test Jig
==================================================
[1/4] Check 1: Shorts to GND ... [PASS]
[2/4] Check 2: Pin Bridges & VCC Shorts ... [FAIL]
  -> ERROR: Bridge detected: driving PA6 (H1-2) pulled down PA7 (H1-3)

--------------------------------------------------
RESULT: FAILED. Do NOT flash final image.
--------------------------------------------------
```
Finally, the real code is flashed over. There's more to say about the actual code, but I'll save that for the next log.

The code for the test jig is here on GitHub.

Here's a video of how using the test jig looks like.
A modular modulus
kbsriram • 09/08/2026 at 18:54 • 0 comments

At the end of the last build, my 3 moduli let 740,000 of 5.68 million candidates through, and the Pico spent 23 minutes checking them. The sieve was idle 92% of the time - filter-bound, generating survivors faster than the Pico could check them.

I need more moduli. Twelve would drop checking to a few seconds, and the 1932 gear machine ran 30. So it's time to leave the breadboard and make each modulus a card I can plug into a backplane.

The hardware

My plan is a stripboard bus with female headers, with each modulus an ATtiny412 on a card standing vertically in it. All pins come out to one edge, with a decoupling cap on the card. I want to keep the UPDI programming pin free. SDA and SCL sit on PA1 and PA2. That leaves PA3, PA6 and PA7 for REQ, VOTE and one spare. PA7 has the peripherals I'm least likely to need, so it drives an onboard LED and each card blinks its own vetoes.

The schematic is an ATtiny412, a decoupling cap, an LED with its resistor, and a header. The one addition is a jumper that ties PA7 to a header pin, in case I want that line off the card instead of the LED.

Routing fits entirely on the top layer. I rounded the traces for the look of a hand-drawn PCB, and rounded one corner so I can check that 30 cards are all seated the same way.

I drew the schematic and board in JLCPCB's online editor and picked parts they stock so the boards arrive assembled. Hand-soldering 30 sets of SMD parts is not something I want to do, so the header pins are all I have to solder.

Thirty boards came to $81 with shipping and tariffs, or around $2.70 a modulus. Each board is identical, since the modulus is loaded over I2C at the start of a run.

Gerbers, Altium source and the JLCPCB BOM are in the GitHub repo if you want to order your own.
Sieving versus checking
kbsriram • 09/06/2026 at 19:14 • 0 comments
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.

Some moduli in the 1932 Lehmer gear sieve: Photographer: Marcin Wichary (CC BY 2.0)

Rejected positions plugged up with toothpicks: Photographer: Marcin Wichary (CC BY 2.0)

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...
Read more »
The sound of sieving
kbsriram • 09/01/2026 at 17:41 • 0 comments

How would you solve an equation like

This isn't too hard of course, we can write

to get all possible x, y pairs. But what if we constrain x and y to be positive whole numbers?

Equations like this are Diophantine Equations, and are known to be hard to solve in the general case - e.g. with arbitrary powers and terms. If it has only squared terms like this (quadratic Diophantine equations) they are still known to be NP-complete, so we don't have any good way to solve them quickly either.

Let's try to brute-force our example anyway.

What we're looking for, are numbers of the type:

which are themselves square numbers, since y needs to be the square root.

Let's check for x = 1 - we get 2*1^2 + 4001 = 4003 - it's not a square number

Let's try a few more

x 0 1 2 3 4 5 6 7 8 9
2x^2 + 4001 4001 4003 4009 4019 4033 4051 4073 4099 4129 4163

You might instinctively notice that some of these numbers - e.g. - 4033 don't look like it could be a square.

In fact, any perfect square ends in 0, 1, 4, 5, 6 or 9. The last digit (in base 10) is just arithmetic modulo 10, and so we can discard about half our numbers without going through the bother of actually calculating the square root.

We can do the same trick with a different base - let's take everything modulo 3, and see where that gets us

x mod 3 0 1 2
x^2 mod 3 0 1 1
2x^2 + 4001 mod 3 2 1 1
could be square? no yes yes

The second row tells us only 0 and 1 can be perfect squares in mod 3 arithmetic.

The third row tells us that 2x^2 + 4001 = 2 mod 3 when x is 0 mod 3, and the second row tells us that 2 can never be a perfect square mod 3.

So this means any x that's 0 mod 3 can't be a solution either.

So we can skip about a third of our brute-force check already.

Let's do this trick for a couple more moduli

x mod 5 0 1 2 3 4
x^2 mod 5 0 1 4 4 1
2x^2 + 4001 mod 5 1 3 4 4 3
could be square? yes no yes yes no

mod 5 lets us avoid checking about 40% of our numbers

x mod 7 0 1 2 3 4 5 6
x^2 mod 7 0 1 4 2 2 4 1
2x^2 + 4001 mod 7 4 6 5 1 1 5 6
could be square? yes no no yes yes no no

mod 7 lets us skip checking around 60% of our numbers.

x mod 11 0 1 2 3 4 5 6 7 8 9 10
x^2 mod 11 0 1 4 9 5 3 3 5 9 4 1
2x^2 + 4001 mod 11 8 10 5 4 7 3 3 7 4 5 10
could be square? n n y y n y y n y y n

and mod 11 lets us skip about 50% of our numbers.

We could of course keep stacking these tests. If we use prime moduli, each new modulus removes about half the candidates, so this gets very effective very fast. If we use k moduli, only about 1/2^k candidates survive the test. (The initial few primes usually remove less than half, so in practice sieves don't bother with moduli smaller than 9.)

The sieving mathematicians

Imagine you have four people in a room - one per modulus. Each of them has just the last row of yes/no values for their table. So we have one person holding the mod 3 row, another holding the mod 5 row, and so on.

A fifth person - a scorekeeper - holds a counter set at 0, and then shouts "vote".

Everyone looks at their first cell - if it says "no" - they shout "no". If it says "yes", they keep silent. Then, they move their finger to the next cell and wait for the scorekeeper. If they get to the end of their row, they just start over.

Most of the time, one or more people would have shouted no, and the scorekeeper just clicks their counter and shouts "vote" again.

Every once in a while, nobody in the room would have veto'ed that number. The scorekeeper looks at their counter, and checks if it could be a solution. If not, they keep moving on.

Let's see how this plays out in our example for the first 10 steps. Notice how the mod 3 and mod 5 rows just repeat every 3 times and 5 times respectively. Each row is just a pattern that repeats with a period equal to its modulus.

scorekeeper 0 1 2 3 4 5 6 7 8 9 10
the mod 3 person N -- -- N -- -- N -- -- N --
the mod 5 person -- N -- -- N -- N -- -- N --
the mod 7 person -- N N -- -- N N -- N N --
the mod 11 person N N -- -- N -- -- N -- -- N

At least one person vetos every number through 10, and the scorekeeper just keeps clicking...
Read more »