We need “random numbers” all the time. They are used in video games, simulations, and of course “encryption”. But, what does it mean to generate a “random” number?
The most intuitive notion is: if I gave you a sequence of random numbers, and asked you to guess the next number, you wouldn’t be able to. Does this remind you of those Mental Ability questions, where you had to identify the next number in a given a sequence? Remember when you couldn’t figure it out and thought, “what a random sequence!”?
That’s actually the key insight. Randomness = no patterns; there’s nothing in the sequence that lets you predict what comes next.
How do you generate a sequence of random numbers? By repeatedly measuring something that doesn’t follow patterns, something that’s inherently unpredictable. For example, you could record the result every time you roll a die, or write down a 1 or 0 each time you flip a coin.
But here’s the problem: imagine you’re developing a video game that needs a million random numbers. Can you picture the hassle of actually making a million observations of unpredictable events? Rolling a die a million times? That’s not practical.
Now, what if you could make just 10 observations of unpredictable events and use those to generate a million random numbers?
That’s exactly what pseudorandom generation does. And here’s the interesting part: this is actually what happens every time you call rand(seed) in Python. It’s not generating truly random numbers – it’s using an algorithm to create numbers that look random, starting from a small seed of true randomness.
But, how do you tell if this pseudorandom generator is working correctly; that it’s actually generating a million random numbers? Here’s one way, which is the essence of modern cryptography. If you were to compare these million random numbers generated by the pseudorandom generator against million random numbers generated by actually making a million observations; you can’t tell the difference.
Now, what if you want to generate a million sequences of a million random numbers? Sure, generating 1 sequence of million random numbers needs only 10 observations of unpredictable events, with pseudorandom generators. But to generate a million sequences, you need a million times 10 observations!
No way, we want to do better. We want to generate these million sequences with only 10 observations. What if, with just 10 observations, we generate a random function that maps each input in {1, 2, …, 10^6} to its own random sequence?
A pseudorandom function allows us to generate this random function. And just like with pseudorandom generators, each sequence it produces should be indistinguishable from a truly random sequence. This is the foundation that makes modern encryption practical – one secret key can generate unlimited independent random sequences of 0s and 1s for encrypting billions of messages.