Transcript Use and Testing of Pseudo-random Number Generators (PRNGs)

Use and Testing of
Pseudo-random Number
Generators (PRNGs)
A. Matthew Amthor
Senior Project 2003
Topical Summary
PRNGs, Linear Congruential
Generators to Combined Hybrid
Generators
 Tests for Randomness, Knuth to
Marsaglia
 Applications for PRNGs

Definition of Generator
From L’Ecuyer
A structure,
Gen  S , so , T ,U , G  , with
S  A finite number of states
so  An initial state or seed
T T :S S
U
(The transition function)
A finite number of outputs
G  G : S U
(The output function)
Definition of Period
The Period, p, for a given generator is the
minimum value of k for which the nth
state of the generator is equal to the
(n+k)th state of the generator.
A finite period is required by the finite
number of states and the function T.
S 
T (s)  s1  T (s)  s2   s1  s2 
p
Linear Congruential Generator
(LCG)
LCGM , a, b, y o 
y n 1  a  y n  b  mod M
Some Popular/Infamous LCGs


LCG 10  11,427419669081,0,1
Maple
> x:=rand();
x := 427419669081
RANDU
Mathematica

LCG
12

,0,1
LCG 231,216  3  65539,0,1
48
  8  1,  231
Properties of the LCG
y n 1  a  y n  b  mod M
S U
G i:x x


Because S  M and T : S  S
defines a function, T, such that a state, s,
uniquely determines the following state,
we can easily say that p  M .
In fact, it has been shown that the maximum
is p=m-1 only if m is prime, the multiplier a is
a primitive root mod M and yo  0.
Extended Linear Congruential
Generator (ELCG aka RG)
LCGM , a0 , a1 ,, ak , b, yo 
yn1  a0  yn  a1  yn1    ak  ynk  b mod M
Also referred to as Recursive Generator (RG).
Note that S  U but rather:
S  ( yn ,, ynk ) | ym U 
And therefore it is no longer true that:
T : S  S   T : U  U  , or that
NOT TRUE!
pM
Combined Linear Congruential
Generator (cLCG)
LCG1 M1 , a1 , b1 , yo1 ,..., LCGk M k , ak , bk , yok 


As before, y1, n 1  a1  y1, n  b1 mod M 1
Methods of Combination
( m)
n
x
Bit wise XOR
( m)
( m)
1,n
2, n
y
y
L’Ecuyer
 J

Z n     j x jn  mod m1
 j 1

  y
( m)
k ,n
(mod 2)
Wichmann & Hill
 J  j x jn 
 mod 1
Un  
 j 1 m 
j 

Wichman and Hill cLCG
LCG1 30269,171,0,1
LCG2 30307,172,0,1
LCG3 30323,170,0,1
Combined Linear Congruential Generators are
equivalent to generators with larger moduli.
LCG27817185604309,16555425264690,0,1
Multiple Recursive Generator
(MRG)
LCG1 M 1 , a1, 0 ,, a1,k , b1 , yo1 ,..., LCGm M m , ak ,, am,k , bm , yom 
Produced by a combination of RGs of the form:
LCGM , a0 , a1 ,, ak , b, yo 
MRG designed by Grube for M  231  1.
Uses 3
generators
Note: definition of indices for coefficients,
a, is off by one from my definition.
Shuffling Outputs,
The Bays-Durham Shuffle
Time to Use the Whiteboard
Feedback Shift Register
(FSR or LFSR)
so  x4 , x3 , x2 , x1  Output is a stream of bits.
0
0
G
0

0
0 0 0
0 0 0
0 0 0

0 0 1
 c4
c
T  3
 c2

 c1
1
0
0
0
0
1
0
0
0
0
1

0
The period is limited by the
number of states.
p  S 1
Note: cn 
0,1n
Hmm…
Full Period LFSR
For Example,
so  1,0,0,1
n4
 c4
c
T  3
 c2

 c1
1
0
0
0
0
1
0
0
0
0
1

0
x n  cn x n 1    c2 x  c1 <-monic irreducable?
x  x  1 is monic irreducable for this n.
4
3
The period then is the smallest m so that
f(x) divides xm + 1. In this case m=15.
That Doesn’t Look Random
Lattice structure exhibited by
any generator based on
multiplicative linearcongruential methods.
(LCG, cLCG, ELCG, MRG, as
well as FSR, and Fibonacci)
Source: pLab website
Lattice structure exists in all
dimensions. (3-d lattice at right)
Inverse Congruential
Generator (ICG)
ICGM , a, b, yo 
yn1  a  yn  b mod M
with
y n such that,
 yn  yn  mod M  1
The ICG shows no lattice structure, though
some symmetries are evident.
Tests for Randomness
Uniform distribution in k-dim space
 Monte Carlo value for pi
 Rank permutation distribution
 Characteristics of spectral lattice
 Selected tests from DIEHARD by
Marsaglia

GCD, value and iterations necessary
 Birthday spacings repeated

Uniform Distribution in
k-dimensions
Divide the space
into N bins of equal
size.
Form a number, P,
of k-tuples from the
random numbers.
Count the number,
n, of k-dimensional
vectors in each bin.
?
nP N P N
Rank Permutation
Distribution
Generate n sets with m random
numbers in each set
(3,5,2)(1,0,8)(1,2,6)(3,0,2)  (6,7,2)
Replace the numbers in each set with
their rank within that set (1..m).
(2,3,1)( 2,1,3)(1,2,3)(3,1,2)  (2,3,1)
Check for a uniform distribution of each
of the m! possible orderings
Monte Carlo Value for Pi
See Maple worksheet:
MonteCPi.mws
Spectral Test
in s-Dimensions
Considers the maximal distance
between adjacent parallel
hyperplanes in the s-dimensional
lattice. The maximum of these
values over all families is ds
(poor 2-d lattice structures)
Images from pLab website; K. Entacher, P. Hallekalek
GCD Test from DIEHARD
a
b
366 = 1*297 + 69
297 = 4*69 + 21
69 = 3*21 + 6
21 = 3*6 + 3
6 = 2*3 + 0
iterations)
GCD(a,b) = 6
(k=5
Applying Euclid’s
algorithm to two integers
will produce several
quantities to examine.
The distributions of k and
GCD(a,b) have been
studied extensively.
Results from GCD Test
For a, b  1,2,, n,
k ~ N 0.842766 ln( n)  .06535, 0.5151ln( n)  .1666


The distribution of GCD(a,b) was found
by extensive simulation.
k
Expected Counts
KISS
Xn=69069*Xn-1+12345 mod 232
5.5
7
3
4
29.5
30
20
5
144.6
142
101
6
590.7
583
491
7
2065
2148
1629
8
6277
6294
4965
154
21
123
701
1896
6121
gcd
Expected Counts
KISS
Xn=69067*Xn-1 mod(235+951)
1
6079271
6078818
6077628
2
1519817
1521176
1520790
3
675474
675496
675940
4
379954
379749
379369
5
243171
242677
243256
6
168869
168462
168537
Xn=69069*Xn-1+12345 mod 232
8106215
0
900376
0
324000
0
Xn=69071*Xn-1mod(232+15)
<=3
Birthday Spacings Test from
DIEHARD
Generate m birthdays in a year of
length n using PRNG outputs.
Poisson distribution approximates
the number of duplicated values
among ordered birthday spacings
asymptotically with   m3 (4n) .
Diehard uses an especially rigerous
n=232 and m=212, such that   4 .
Results from B’day Test
KISS Generator
0
91.6
87
4.6
1
366.3
385
18.7
2
732.6
748
15.4
Expected vs. Observed counts
3
4
5
976.8
976.8
781.5
962
975
813
14.8
1.8
31.5
p-value=
6
521
472
49
7
297.7
308
10.3
0.705
8
148.9
159
10.1
9
66.2
61
5.2
>=10
40.7
30
10.7
1.000
8
148.9
489
340.1
9
66.2
319
252.8
>=10
40.7
384
343.3
1.000
8
148.9
0
148.9
9
66.2
0
66.2
>=10
40.7
0
40.7
yn   yn 55  yn  24  mod 232
0
91.6
15
76.6
1
366.3
60
306.3
2
732.6
255
477.6
Expected vs. Observed counts
3
4
5
976.8
976.8
781.5
470
691
837
506.8
285.8
55.5
p-value=
6
521
814
293
7
297.7
666
368.3
yn  214013  yn 1  2531011 mod 232
0
91.6
2112
2020.4
1
366.3
1797
1430.7
2
732.6
815
82.4
Expected vs. Observed counts
3
4
5
976.8
976.8
781.5
221
46
8
755.8
930.8
773.5
p-value=
6
521
0
521
7
297.7
1
296.7
Selected Applications
Monte Carlo simulations
 Cryptography
 Computational number theory

Monte Carlo Simulations
For Radioactive Decay Simulation
See Maple worksheet:
MonteCDecay.mws
Cryptography
Public Key:
Private Key:
Decrypts info
encrypted with
the public key
Used to encrypt
info sent to you
PRNGs are used to
generate secret keys.
Emphasis is on
unpredictability.
What to Look for in a
Cryptographic PRNG
Assume attackers will know your
generator algorithm.
Very large number of states
Strong separation between the state
value and the output value
Reseeding process or other means of
adding entropy continuously to the state
Cryptographic Generator:
DSA PRNG
S  X i | X i  Z 216 0 
(least states used in DSA)

G  X i ,Wi   hash Wi  X i mod 2160

Wi  Optional Input
(state is “hidden” in output)

X i 1  X i  G  X i ,Wi   1 mod 2160

(new state incorporates optional input)
Computational Number
Theory
Additional properties of purely random
numbers are required beyond uniform
distribution.
Outputs should have prime factorizations
and relative GCDs consistent with a purely
random generator.
References
J. Woods, personal communication.
E. Green, personal communication.
P. Patten personal communication.
G. Marsaglia and W. Tsang, 2002, Some Difficult-to-pass Tests of
Randomness, Journal of Statistical Software, Volume 7, Issue 3.
C. C. Klimasauskas, 2002, Not Knowing Your Random Number
Generator Could Be Costly: Random Generators – Why Are They
Important , PCAI, Volume 16, Number 3.
Pierre L’Ecuyer, 1994, Uniform Random Number Generators,
Annals of Operations Research.
J. Kelsey, B. Schneier, D. Wagner, and C. Hall, Cryptanalytic
Attacks on Pseudorandom Number Generators,
http://www.counterpane.com/pseudorandom_number.pdf
References (cont.)
Diehard Program and Associated Documentation by G.
Marsaglia, http://stat.fsu.edu/pub/diehard/
D. M. Ceperley, 2000, Random Number Generation,
http://web.mse.uiuc.edu/matse390/lnotes/PRNG.ppt
Spectral Test Server, K. Entacher, P. Hellekalek,
http://random.mat.sbg.ac.at/results/karl/spectraltest/,
http://random.mat.sbg.ac.at/~charly/server/node1.html,
W. Cherowitzo, Linear Feedback Shift Registers, 2000,
http://wwwmath.cudenver.edu/~wcherowi/courses/m5410/m5410fsr.html
Sieve of Eritosthenes,
http://www.math.utah.edu/~alfeld/images/sieve.gif
References (cont.)
C. E. Praeger, Linear Feedback Shift Registers, 2001,
http://www.maths.uwa.edu.au/~praeger/teaching/3CC/WWW/cha
pter4.html
Unknown Author, Statistical Tests,
http://sprng.cs.fsu.edu/Version2.0/statistical-tests.html
Unknown Author, Teaching Notes for the
Probabilistic Number Theory Problem,
http://www2.edc.org/makingmath/mathprojects/pNumberTheory/
pNumberTheory_teach.asp
Unknown Author, Linear Feedback Shift Registers,
http://homepage.mac.com/afj/lfsr.html
And a very special thanks goes to Mr.&Mrs.