How Decoding Works (Backwards Magic)
Given a prime and a tiny key, we can recover the original name. Here's exactly how the puzzle runs in reverse.
For most of A Prime for You’s history, getting a prime back into a name was impossible. The earlier algorithms used a one-way recipe — your name went in, a prime came out, and there was no path in reverse. Charming in its way, but final.
The a3.0 algorithm changed that. Now, given a prime number and the matching three-character key, we can run the puzzle backward and recover the original name. The math doesn’t care which direction it flows.
Here’s how the reverse trip works.
You’ll need three things
To decode an a3.0 prime, the decoder needs:
- The prime number itself
- The 3-character key that was issued with it
- The algorithm version (so it knows which puzzle it’s solving — currently
a3.0)
That’s it. No extra clues, no lookup table, no central server pinging a database. Everything required to recover the name lives in those three pieces of input.
Step one: figure out the size of the box
The first thing the decoder does is look at the prime’s bit length. Was it a 64-bit number? 96? 128? Each block size has a different bit layout, and we have to pick the right one before we can do anything else.
There’s a small trick that makes this reliable: at generation time, the topmost bit of every block is forced to be 1 — the block-size pin. That guarantees the resulting prime falls cleanly into one of three known bit-length ranges, with no ambiguity at the boundaries. Without the pin, a 96-bit block whose top bit happened to be zero would look exactly like a 64-bit one, and decoding would start by getting the structure wrong.
A small, deliberate piece of bookkeeping. Pays off enormously here.
Step two: undo the scramble
Now we run the Feistel scrambler — the same one that produced the prime — in reverse, using the supplied key. The same machinery that scrambled the bits unscrambles them. Same hardware, same key, opposite direction.
What comes out is the plaintext block: the bits that went in, before any scrambling happened. That block contains, in fixed positions:
- The pin bit (still 1)
- A 6-bit count of how many characters are in the name
- The Huffman-encoded characters
- The leftover nonce bits from the prime hunt
(If the key is wrong, the bits we get out are essentially random. The decoder will notice almost immediately — usually because the character count comes out as nonsense, or the Huffman walk hits a dead end. Wrong keys don’t quietly produce wrong names; they produce no name at all.)
Step three: read the count, then the letters
The decoder pulls out the 6-bit count first — exactly N characters in this name — and now it knows when to stop.
Then it walks the Huffman tree. The Huffman bits are a stream of variable-length codewords — 010 might mean E, 1100110 might mean Q — so the decoder reads bits one at a time, following the tree until it lands on a letter, emits that letter, and starts again from the root for the next one. After exactly N characters, it stops.
Whatever bits are left over after that? They’re the nonce — the wiggle-room from the prime hunt. They have no meaning in the recovered name. The decoder simply ignores them.
Why this is harder than it sounds
The whole reversibility trick depends on two properties of the bit layout, and if either one were missing it wouldn’t work:
- The pin is at a fixed position. It’s always the topmost bit. Without it, we couldn’t infer the block size from the prime alone.
- The count prefix is at a fixed position. It’s always 6 bits, at a known offset. We need to know how many characters to decode before we start walking the Huffman tree, because Huffman codewords don’t have natural endings — without a count, we wouldn’t know whether the next bits are the start of another letter or just nonce.
So the layout isn’t decorative. It’s the architecture that lets the reverse trip exist at all.
A small, careful piece of magic
When you watch a decode succeed, it feels a bit like sleight of hand: a string of digits goes in, a name pops out, and there’s no obvious mechanism in between. But like any good magic trick, it’s all engineering once you know how. A predictable bit layout, a reversible cipher, the right key, and a Huffman tree willing to be walked backward.
Run all four in order. Out comes the name. Every time.