Transcript Random Numbersx

Generating Random Numbers
a presentation by:
Matthew Jobrack
What is randomness?
Governed by, or involving equal chance for each
item.
Two Categories
There are two basic categories of methods for
generating random numbers:
1. Physical Methods (Hardware Random Number Generation)
2. Computational Methods
3. Humans (really bad at this)*
We will now take an adventure through each of these methods,
and then discover how randomness is tested!
Physical Methods
• The most early, primitive forms of random
number generation (originally used for
gambling) fell into this category.
• This includes methods such as dice rolling,
coin flipping and other things you might still
see in gambling today.
• These methods can be pretty random, but
very slow, and can have several other
problems.
Physical Methods
• In modern times, several physical methods
have been discovered to generate random
numbers, usually based on natural
phenomena that are inherently unpredictable.
Physical Methods
These methods include:
1. Measuring time intervals between
radioactive decays using a Geiger counter.
2. Clock drift (minute differences in
synchronized clocks)
3. White noise on a radio
Physical Methods
• Hardware random number generation is safer
for encryption purposes.
• However, in many cases it is less practical.
• Physical random number generators are also
prone to “breaking” and becoming less
random, with no obvious signs that it has
done so.
Computational Methods
• Pseudo-Random number generators (PRNG)
are algorithms designed to produce a
sequence of numbers that pass tests for
statistical randomness.
• They are programmable algorithms though,
and are therefore not completely random.
• If you used these enough, you would begin to
find periodic patterns. They approximate the
properties of random numbers.
Computational Methods
There are several advantages to PRNGs:
1. They are programmable, and therefore
obviously very convenient.
2. They are reproducible.
3. They are much faster.
Computational Methods
There are many different types of PRNGs,
including but not limited to:
1. Middle Square Method
2. Lagged Fibonacci Generators
3. Linear Congruential Generators
4. Mersenne Twister
5. Linear Feedback Registers
6. Blum Blum Shub
Middle Square Method
For a generator of n-digit numbers, the period using this method can be no
longer than 8n.
All this method involves is squaring a number, then taking its middle digits.
Ex.
• To generate 6-digit numbers, start with a random seed, say, 675248.
• Square this number to get: 455959861504.
• Take the middle 6 digits of this number to get the next random number:
959861.
This method has several problems, one of which is that the sequence of
numbers often converge to 0.
Lagged Fibonacci Generators
Random numbers generated by:
*
Sn º Sn-j *Sn-k (modm),0 < j < k
Where
is some binary operation.
m is often a power of 2, such as 232 or 264. This is to help a computer
calculate faster, because if m is 2p, the computer can divide by 2p and
calculate the remainder by truncating all but the rightmost 2p digits.
The maximum period depends on the binary operation used, and on values of
j and k. This means that arbitrarily choosing j and k may not result in a very
random sequence.
Using this method, a computer must also keep track of the previous k
numbers in the sequence.
Linear Congruential Generators
Random numbers generated recursively by:
Xn+1 º (aXn + c)(mod m)
Again, choosing m to be a power of 2 is the most efficient choice, in terms of
computer power. However, choosing this modulus can lead to less randomness.
The period length is at most m, but whether or not the sequence achieves a
period of this length is very sensitive to the choices of a and c.
In particular, the period length will be m iff:
• c and m are relatively prime, and
• a-1 is divisibe by all prime factors of m
• a-1 is a multiple of 4 if m is a multiple of 4
Linear Congruential Generators
Advantages:
• They are very easily (quickly) calculated
• The are decently random
Disadvantages:
• Not super random
• In particular, there is a serial correlation between successive values. If we
plot successive 3 points on a 3 dimensional plot, they will not be truly
random points, and will lie on various planes.
• The RANDU number generator, which uses the recurrence
X j+1 = 65539· X j (mod 231 )
Was used in the 60’s and 70’s, before people realized that it fails
practically every random number test.
Mersenne Twister
•
•
•
•
•
Can produce a period of 219937-1 with the correct choice of parameters.
Passes almost all tests for statistical randomness.
Uses a working area of only 624 words.
There are no efficient algorithms with integers using a Mersenne twister.
The Mersenne twister uses polynomial algebra over the two-element
field.
• The recurrence is defined:
l
Xk+n := Xk+m Å (Xku | Xk+1
)A
–
For k=(0,1,2,..). The seed is given as x1, x2, …, xn-1.
Blum Blum Shub Method
If M is the product of 2 large primes which are
congruent to 3 (mod4), then this method is the
recurrence:
2
Xn+1 = Xn mod(M )
The seed should be chosen such that it is
coprime to M.
• This PRNG is notable because each number in
the sequence can be calculated directly.
Tests for Randomness
•
•
•
•
•
Frequency test
Serial test
Poker test
Gap test
Diehard tests