Prime Hunting With Tiny Tweaks

By this point, the puzzle machinery has done quite a lot. Your name has been tidied, packed into bits, and the Feistel scrambler is ready to lock everything up with your key.

There’s one thing left, and it’s the whole point of the exercise: the result has to be a prime number.

If we just packed your name into bits and ran them through the scrambler once, we’d get a number — sure, fine, a number — but the chances that it would happen to be prime are about the same as drawing a particular card from a deck of fifty. It would work occasionally and let everyone down the rest of the time.

So we built a small search.

A tiny window of free bits

Inside every block, alongside the bits that encode your name, there’s a region we call the nonce. It’s a small range of bits — at minimum 9, sometimes more — that don’t carry any meaning. They’re just spare digits we get to play with.

Here’s the loop, in plain language:

1. Pick a value for the nonce. Start with 0.
2. Glue together the pin bit, your character count, your Huffman bits, and the nonce. That’s our candidate plaintext block.
3. Run it through the Feistel scrambler with your key. Out pops a candidate ciphertext.
4. Ask the Miller–Rabin primality test: is this number prime?
5. If yes — beautiful, we’re done. That’s your prime.
6. If no — bump the nonce up by one, and try again.

Repeat until a prime falls out. Move on.

Why we usually find one quickly

Primes might feel rare — they’re scattered unpredictably across the number line — but at the sizes we care about (64, 96, or 128 bits), they’re not actually that hard to bump into. The Prime Number Theorem gives a useful estimate: among numbers near N, roughly 1 in ln(N) of them are prime. For a 128-bit number, that works out to about 1 in 89 candidates being prime.

So on average we expect to try around 89 nonces before something works. With 9 bits of nonce headroom we have 512 candidates to try, which is comfortably more than we typically need. For 96-bit primes the average is more like 1 in 67. For 64-bit primes, about 1 in 44.

Most names find their prime in a tiny fraction of a second.

A safety net at 4,096 attempts

But “on average” isn’t “always.” Probability is mischievous. So we set a hard cap: 4,096 attempts, and then we give up.

In practice we essentially never hit it. The chance of failing 4,096 Miller–Rabin tests in a row, when each one had a roughly 1-in-89 chance of succeeding, is astronomical — small enough that if it happens, it’s worth investigating as a bug rather than a coincidence. But the cap is there because no software loop should be allowed to run forever, and we’d rather return an honest error than spin a CPU until the heat-death of the universe.

Why your prime isn’t your friend’s prime, even if you share a name

Two people named Maria Santos will not get the same prime. That’s because they’ll get different keys. A different key feeds a different scrambler. The same starting bits, scrambled by a different key, land on different candidate values — which means the search starts in a different neighborhood of the number line and lands on a different prime.

This is a feature, not a coincidence. It means every prime in the registry is genuinely tied to its owner — not just to their name but to the specific moment they bought it.

What you actually own

The prime on your certificate isn’t the raw “this is what the bits literally say” number. It’s the first scrambled value, in a search starting from your encoded name and key, that happened to be prime.

That’s a small distinction with a big consequence: the math that produced it is reversible (if you have the key), it’s verifiably prime (Miller–Rabin doesn’t lie), and it’s almost certainly yours alone. We didn’t pick it. Your name picked it. We just helped with the search.