Pseudo-Random Number Generators in Maple

Michael Monagan

June 21st, 2004.

Maple's pseudo random number generator "rand" is a linear congruential
generator (LCG) which computes a sequence x[1], x[2], ... using

              x[k+1] = a x[k] mod p

where p is a 12 digit prime and a is a primitive element in Z mod p, hence,
the period pi of the generator is 10^12-12.  The Blum-Blum-Shub (BBS)
generator is a quadratic congruential generator of the form 

              x[k+1] = x[k]^2 mod n 

where n is a product of two primes and it uses only the least significant
bit of the x[1], x[2], ...

In this talk I will first show why an LCG is not suitable for cryptographic
applications and in fact why the sequence x[1], x[2], x[3], ... is not very
random at all.  Then I will define the requirements for a ``cryptogrpahically
secure pseudo-random number generator.''  Blum, Blum and Shub show that 
their generator meets these requirements if integer factorization and the
quadradic residue problems are computationally unsolvable.

For cryptographic applictions one also needs that the sequence x[1], x[2], ...
has along period.  I will show how to choose the primes so that the period 
will be large even when the user does not know the factorization of n.
Finally, I give a Maple code for a 10 digit prime version of the BBS generator.
This is not cryptographically secure.  But, the random numbers will be very
good, the period large, and since (by experiment) it's about as fast as Maple's
rand command, we obtain a better pseudo-random number generator for Maple.

This is joint work with Greg Fee.