Introduction

True randomness is surprisingly hard to come by. Computers are deterministic machines — feed them the same input and they always give the same output. Yet almost everything secure, from your encrypted messages to the lottery, needs a steady supply of unpredictable bits.

The fix is a pseudorandom generator (PRG): a small, deterministic program that takes a short truly-random seed — say 128 coin flips — and stretches it into a much longer stream of bits. The stream isn't really random; it's completely determined by the seed. And yet, to anyone who doesn't know the seed, it looks perfectly random.

That's the whole trick, and it's the foundation of every stream cipher: keep one short secret, and you can generate a keystream as long as the message you want to hide.

Stretch a Seed

Pick a short seed below and press Expand. A tiny deterministic generator stretches your few starting bits into a long stream, and three simple randomness tests check whether the output looks like fair coin flips: roughly half ones, no obvious short-run bias, and no easy correlation between neighboring bits.

<p class="hint">A pseudorandom generator stretches a short <b>seed</b> into a long
stream of bits. Pick a seed, press <b>Expand</b>, and watch three simple randomness
tests judge the output. The same seed always gives the same stream — but flip one bit
of the seed and everything changes.</p>
<div class="row">
  <label for="seed">Seed (digits):</label>
  <input id="seed" type="text" value="42" maxlength="12" inputmode="numeric">
  <button id="flip" type="button" class="ghost">Flip a seed bit</button>
</div>
<div class="btns">
  <button id="expand" type="button">Expand</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="stream" id="stream">Press Expand to generate a stream.</div>
<div class="tests" id="tests"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.row { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
label { font-size: .9rem; font-weight: 600; color: #1d3557; }
input { font: 600 14px ui-monospace, monospace; padding: .4rem .6rem; width: 9rem;
        border: 1px solid #cdd9e3; border-radius: 8px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.stream { font: 600 13px ui-monospace, monospace; line-height: 1.7; letter-spacing: 1px;
          background: #f4f7fa; border: 1px solid #e1e8ef; border-radius: 8px; padding: .7rem;
          word-break: break-all; color: #1d3557; min-height: 3.5em; }
.stream b { color: #e63946; }
.tests { margin-top: .7rem; display: grid; gap: .4rem; }
.test { display: flex; align-items: center; gap: .5rem; font-size: .9rem; }
.badge { font: 700 12px system-ui, sans-serif; padding: .15rem .5rem; border-radius: 999px; min-width: 4.2rem; text-align: center; }
.badge.pass { background: #d7f0df; color: #0a7d33; }
.badge.fail { background: #fcdcdf; color: #c92f3c; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A pseudorandom generator (PRG): a deterministic function that stretches a short
// seed into a long bit stream that looks random to anyone who doesn't know the seed.
// Here we use a small mixing function (a SplitMix64-style hash) in counter mode:
//   for i = 0,1,2,...   output_block = mix(seed + i)
// Crucially it is DETERMINISTIC: same seed -> same stream. Secure real-world PRGs
// (stream ciphers) replace this toy mixer with a hardness-based one-way function.
const STREAM_BITS = 256;

// Murmur3-style 32-bit finalizer: a strong mixer that avalanches its input, so
// flipping ANY single input bit flips about half of the 32 output bits.
function mix(x){
  x = (x + 0x9e3779b9) >>> 0;
  x = Math.imul(x ^ (x >>> 16), 0x85ebca6b) >>> 0;
  x = Math.imul(x ^ (x >>> 13), 0xc2b2ae35) >>> 0;
  x = (x ^ (x >>> 16)) >>> 0;
  return x >>> 0;
}
// Stretch a numeric seed into n pseudorandom bits via counter mode:
// block i = mix(seed XOR (i * golden-ratio constant)), 32 fresh bits each.
function expand(seed, n){
  const bits = [];
  let counter = 0;
  while (bits.length < n){
    const block = mix(((seed ^ Math.imul(counter + 1, 0x9e3779b9)) >>> 0));
    for (let b = 31; b >= 0 && bits.length < n; b--) bits.push((block >>> b) & 1);
    counter++;
  }
  return bits;
}

// ── Three simple randomness tests ───────────────────────────────────────────
// 1) Frequency: the fraction of ones should be close to 1/2.
function freqTest(bits){
  const ones = bits.reduce((a,b)=>a+b,0);
  const frac = ones / bits.length;
  return { ok: Math.abs(frac - 0.5) < 0.08, detail: fmt('%v%% ones', { v: (frac*100).toFixed(1) }) };
}
// 2) Runs: count maximal runs of equal bits; for random bits it's ~n/2.
function runsTest(bits){
  let runs = 1;
  for (let i=1;i<bits.length;i++) if (bits[i]!==bits[i-1]) runs++;
  const expected = bits.length/2;
  return { ok: Math.abs(runs - expected) < expected*0.25,
           detail: fmt('%runs% runs (≈%expected% expected)', { runs: runs, expected: expected }) };
}
// 3) Serial correlation: neighboring bits shouldn't predict each other.
function corrTest(bits){
  let agree = 0;
  for (let i=1;i<bits.length;i++) if (bits[i]===bits[i-1]) agree++;
  const frac = agree/(bits.length-1);
  return { ok: Math.abs(frac - 0.5) < 0.08, detail: fmt('%v%% adjacent pairs match', { v: (frac*100).toFixed(1) }) };
}

let prevBits = null;
function readSeed(){
  const raw = document.getElementById('seed').value.replace(/\D/g,'') || '0';
  return (parseInt(raw,10) >>> 0);
}
function render(bits, prev){
  const el = document.getElementById('stream'); el.innerHTML = '';
  const shown = bits.slice(0,128);
  shown.forEach((bit,i)=>{
    const changed = prev && prev[i] !== undefined && prev[i] !== bit;
    if (changed){ const b=document.createElement('b'); b.textContent=bit; el.appendChild(b); }
    else el.appendChild(document.createTextNode(String(bit)));
  });
  el.appendChild(document.createTextNode(' …'));
}
function renderTests(bits){
  const defs = [
    ['Frequency', freqTest(bits)],
    ['Runs', runsTest(bits)],
    ['Correlation', corrTest(bits)]
  ];
  const c = document.getElementById('tests'); c.innerHTML='';
  defs.forEach(([name,res])=>{
    const row=document.createElement('div'); row.className='test';
    const badge=document.createElement('span');
    badge.className='badge '+(res.ok?'pass':'fail');
    badge.textContent=res.ok?'PASS':'FAIL';
    const txt=document.createElement('span');
    txt.innerHTML='<b style="color:#1d3557">'+name+'</b> — '+res.detail;
    row.appendChild(badge); row.appendChild(txt); c.appendChild(row);
  });
}
function run(){
  const seed = readSeed();
  const bits = expand(seed, STREAM_BITS);
  render(bits, prevBits);
  renderTests(bits);
  console.log('seed', seed, '→ first 32 bits', bits.slice(0,32).join(''));
  prevBits = bits;
}
function flipBit(){
  const seed = readSeed();
  const flipped = (seed ^ (1 << (Math.floor(Math.random()*8)))) >>> 0;
  document.getElementById('seed').value = String(flipped);
  run();
}
document.getElementById('expand').addEventListener('click', run);
document.getElementById('flip').addEventListener('click', flipBit);
document.getElementById('reset').addEventListener('click', ()=>{
  document.getElementById('seed').value='42'; prevBits=null; run();
});
run();
Result
Console

Two things to notice. First, the same seed always produces the same stream — that's what lets two people who share a seed generate the identical keystream to encrypt and decrypt. Second, flip a single bit of the seed and the entire stream changes unrecognizably, yet it still passes the tests. The output is fully determined, but it behaves like randomness — and that is exactly what "pseudorandom" means.

The Real Complexity

The simple tests in the demo are easy to pass — and easy to fool. The real definition of a secure PRG is far stronger and far subtler.

  • The bar is "no efficient test". A generator is cryptographically secure if no efficient algorithm (running in polynomial time) can tell its output apart from a truly random string with better than negligible advantage. This is called computational indistinguishability: the stream may be perfectly predictable in principle, but no feasible computation can exploit that.
  • It rests on hardness, not magic. Such generators are built from one-way functions — operations easy to compute but believed hard to invert. The landmark result of Håstad, Impagliazzo, Levin and Luby (1999) proved that a secure PRG exists if and only if a one-way function exists.
  • Status: conjectured, not proven. We have strong candidates (built on factoring, discrete logarithms, or hardened block ciphers like AES), but no one has proven that any secure PRG truly exists. Such a proof would settle that one-way functions exist — which would immediately imply P ≠ NP, one of the great open problems.
  • The cost of distinguishing. Breaking a good PRG means either learning the seed or finding a statistical edge — and for the best designs, the only known attack is brute force over all possible seeds, which is astronomically expensive.

So a pseudorandom generator lives in a fascinating place: provably useful the moment any one-way function exists, yet its unconditional existence is tangled up with the deepest unsolved question in computer science.

Where It Matters

Once you can manufacture convincing randomness from a tiny seed, it shows up nearly everywhere:

  • Stream ciphers: the canonical use. XOR your message with a PRG-generated keystream and you have encryption; the receiver, sharing the seed (the key), regenerates the same keystream to decrypt.
  • Keys, nonces and salts: the cryptographically secure RNGs in your operating system and browser are PRGs, periodically reseeded from real entropy, that feed every key and session token.
  • Simulation and sampling: Monte Carlo methods, randomized algorithms and games all need fast, reproducible pseudorandom streams — and reproducibility (same seed → same run) is a feature, not a bug.
  • Derandomization: in theory, strong PRGs let us replace true randomness in algorithms with cheap pseudorandomness, a central idea linking randomness and computational hardness.

The same hardness that makes a generator secure is studied directly in factoring and discrete logarithms — the very problems many PRGs are built upon.

Conclusion

A pseudorandom generator does something almost paradoxical: it takes a handful of genuinely random bits and produces an endless stream that acts random to anyone without the seed, even though it's fully determined. That single capability is what turns a short key into a long keystream and makes practical encryption possible.

But peel back the construction and you reach bedrock uncertainty. We can build a secure generator the instant one-way functions exist — yet proving they exist would crack P vs NP wide open. Until then, the randomness protecting your messages is a brilliant, well-tested bet against the limits of computation.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/pseudorandom-generators/Content licensed under CC BY-NC 4.0.