Pseudorandom Generator (PRG)

Updated 12 Aug 2026

•
Definition
- •
  a deterministic, efficiently computable function $G$ that stretches a short random seed (from $\{0,1\}^s$ ) into a much longer output (in $\{0,1\}^n$ , with $n \gg s$ ) that "looks random"
•
Key properties
- •
  efficiently computable by a deterministic algorithm — all the randomness lives in the seed, not in $G$ itself
- •
  the output should be indistinguishable from truly random, to any efficient observer — see Statistical Test
•
How it's used: building a Stream Cipher
- •
  use the seed as the secret key; expand it with $G$ into a long pseudorandom pad; XOR that pad with the message, exactly like a One-Time Pad but with a short key — see Stream Cipher
•
Related

Linked references 8