how it works

background

In 1931, Kurt Gödel showed that any formal statement, a proof, a theorem, a program, can be mapped to a unique natural number. Treat the symbols as digits in some base and read the whole thing as one big integer. Gödel numbering was invented to reason about mathematical logic, but the idea works on any sequence of bytes.

In 2001, Phil Carmody encoded the banned DeCSS DVD-decryption program as a 1401-digit prime. His point was simple: you can't make a number illegal. He chose a prime because numbers feel more incontrovertibly mathematical than software, and a prime more so than a plain integer.

Seth Schoen took it further. He wrote a 456-line haiku sequence whose syllable counts, read as digits, produce a number that is both prime and the DeCSS source code. Then he set it to music, with each digit mapped to a note. The same data in three forms.

godelify lets you do this with anything. Drop in a photo, a text file, a binary. You get back a prime that encodes it exactly and can be decoded without loss.

encoding — step by step

1. Read the input as raw bytes, either file contents or UTF-8 text.
2. Compress with zlib. This shrinks the data and also ensures the first byte is never zero (zlib headers start with 0x78), so no leading bytes disappear when converting to an integer.
3. Read the bytes as a big-endian integer N.
4. Shift left by 32 bits: base = N << 32. The bottom 32 bits are now free to use as a suffix.
5. Find a prime by trying candidate = base | m for m = 0, 1, 2, ... The suffix m is the metadata. The prime number theorem says you'll find one within roughly ln(candidate) tries, usually a few tens of thousands for typical files.
6. Done. The metadata lives in the lower 32 bits and gets stripped during decoding.

// worker.js — encoding loop
const payload = compressOn ? pako.deflate(bytes) : bytes;
const base    = bytesToBigInt(payload) << 32n;

for (let m = 0n; m < (1n << 32n); m++) {
  const candidate = base | m;
  if (isPrime(candidate)) { prime = candidate; break; }
}

bytes ↔ BigInt

We convert through a hex string and let the browser's native BigInt parser do the heavy lifting. Big-endian just means the most significant byte comes first, same as how you'd read a number.

function bytesToBigInt(bytes) {
  let hex = '';
  for (const b of bytes) hex += b.toString(16).padStart(2, '0');
  return hex ? BigInt('0x' + hex) : 0n;
}

function bigIntToBytes(n) {
  let hex = n.toString(16);
  if (hex.length % 2) hex = '0' + hex;
  const out = new Uint8Array(hex.length / 2);
  for (let i = 0; i < out.length; i++)
    out[i] = parseInt(hex.slice(i * 2, i * 2 + 2), 16);
  return out;
}

primality testing

Trial division won't work on a thousand-digit number. You'd run out of time long before finding a factor. Instead godelify uses the Miller-Rabin primality test, which can confidently declare a number prime in a handful of modular exponentiations.

the algorithm

Factor n - 1 as 2^r · d with d odd. Pick a witness a and compute x = ad mod n. If x is 1 or n - 1, the number passes for this witness. Otherwise keep squaring x. If you hit n - 1 before squaring r - 1 times, it passes. If you get through all of it without hitting n - 1, the number is definitely composite.

function modpow(base, exp, mod) {
  let r = 1n;
  base %= mod;
  while (exp > 0n) {
    if (exp & 1n) r = r * base % mod;
    exp >>= 1n;
    base = base * base % mod;
  }
  return r;
}

function millerRabinRound(n, a) {
  const A = BigInt(a);
  if (n === A) return true;
  let d = n - 1n, r = 0n;
  while (!(d & 1n)) { d >>= 1n; r++; }
  let x = modpow(A, d, n);
  if (x === 1n || x === n - 1n) return true;
  for (let i = 0n; i < r - 1n; i++) {
    x = x * x % n;
    if (x === n - 1n) return true;
  }
  return false;
}

deterministic witnesses

One witness isn't enough. Some composites are good at passing the test for specific values of a, so we run it with 13 fixed witnesses: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]. That set covers all integers up to about 3.3 × 10²⁴ with certainty. For larger numbers the chance of a false positive is less than 4^-13, roughly 1 in 67 million.

function isPrime(n) {
  if (n < 2n) return false;
  for (const s of SMALL) {          // trial-divide by 2,3,5,…,41
    if (n === s) return true;
    if (n % s === 0n) return false;
  }
  return WITNESSES.every(a => millerRabinRound(n, a));
}

decoding

Right-shift the prime by 32 to drop the suffix, convert back to bytes, decompress. Nothing extra needs to be stored. The zlib header in the data itself tells the decompressor where things end.

// godelify.js — decode path
const prime    = BigInt(inputString);
const shifted  = prime >> 32n;          // strip metadata suffix
const bytes    = bigIntToBytes(shifted); // BigInt → Uint8Array
const original = pako.inflate(bytes);   // zlib decompress

why a prime?

Any integer would technically work. You could skip the prime search and still recover the file perfectly. The primality is the point. Phil Carmody chose a prime because it feels more incontrovertibly mathematical than software. Hard to argue a prime number is contraband.