|
Pseudo-Random Number Generators in MapleMichael Monagan
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. |