Now, first of all what is random? It turns out that there are an awful lot of
definitions of random. And there are two major ones
that are very widely used. The first one is
statistical randomness. If you look at a sequence
of bits, zeros and ones. With statistical randomness,
the rule is that there'll be an equal probability that the next bits you get
will be zero or one. So in other words,
it's equally likely to be zero as it is to one. And then it has to pass certain statistical tests
for randomness. But once you've done that, you've got a good
statistically random sequence of bits that you can use
a simulation search. The problem is these bits
are often generated by algorithms and as
such are predictable. This takes us to another type
of cryptography, another type of randomness
called kolmogorov randomness or
cryptographic randomness. That adds the requirement that, given perfect knowledge
of every bit that has been generated in
the sequence so far, you cannot predict what
the next bit will be. And the difference between it and statistical randomness is given a perfect knowledge
of every bit that has been generated
in the past for the sequence with statistical randomness,
there's an algorithm. And so you can figure
out the algorithm and then just figure out whether the next bit is zero or one. It's equally likely to be both, but there is an algorithm that
allows you to predict it. With cryptographic randomness,
you can't have that. And the reason
that's important is because for example in
generating cryptographic keys, if you know what one key is and you can predict
the next few bits, you can reduce
the space the number of keys you have to search
to get the next key, or eliminate it entirely
and just know what it is. Both cryptographic randomness
you can't do this. Now, here's an interesting
and amusing comic that illustrates this point. It's from Scott Adams Dilbert. And the comic is, Dogbert
asked to generate a sequence of
random numbers, integers. Dogbert says, okay 9, 9, 9, 9, 9, 9, 9, 9, 9 and so forth. Dilbert expresses incredulity and says, are those really random? Now the question is,
could this actually occur with a real random
number generator? Surprisingly the answer is yes. Because given a sequence
of numbers in the past, it would be equally
likely to be any one of the digits, zero to nine. And it could be nine, this is called the rand. And if you look for example at the decimal representation
of the number pi. In pi, there are a number of rands of nines and
other numbers too, yet pi is transcendental and the numbers in the digits in its representation are
often treated as random. By the way they're
not really random, they're pseudorandom
because once you figure out that it's
the digits in pi, you can predict the
next one quite easily. So, the distinction between
random and pseudorandom. If it's statistically random, then it's pseudorandom for the purposes for which
we're using the term. Pseudorandom means it's
produced by an algorithm that generates a series of bits
that appear unpredictable, but in fact are computed
from an algorithm. The pseudorandom
number generators typically maintain what's
called internal state, which tells them how to
generate the next number. Every time something is output, every time you output a
bit, the state changes. And what the pseudorandom
number generates, you have to start somewhere. So you have an initial state. This is called the seed. Sometimes you just get a
little short stringing you generate the initial
actual initial state from it. But the point is wherever
you start, that's the seed. If I can guess the seed, I can generate
the entire sequence. On the other hand,
a random sequence of bits is something that's not generated by a deterministic algorithm. It's usually
some physical phenomena. For example certain
aspects of hardware. Rand did a very
famous collection of numbers by measuring output, rather by measuring
changes in radiation level from the nuclear testing
in the fifties. And even there they had
to touch it up a little bit to make it usable. But the point is
the atomic background is random. White noise is another very
good way to generate it. White noise is simply what you
hear when there's nothing, when you don't hear sounds. How discs do seeks or rather the variance and times
is often random as well. So there are a number of ways
to get it from hardware. And once you've
generated them bits, there may be a deterministic
algorithm applied to add some more
uncertainty, that's fine. But the point is, the algorithm doesn't start from a seed.
It's not predictable. It starts from a set of random
numbers or random bits. And so, you don't know
what's going to come out even if you know
everything previously. A good way to look at this
is if you're going to test something that
uses random numbers, you want pseudorandom numbers because that way you can repeat the same sequence over and over just by using the same seed. On the other hand when it
rolls into production, you're going to want real random numbers and that's when you use a real random number generator rather than a pseudorandom
number generator. Because if you can repeat
it, it's pseudorandom. It is not random.