The complete reference is Moreau, Thierry, A practical 'perfect' pseudo-random number generator, article submitted to Computers in physics, 1996.
The "x² mod N" generator, also known as the BBS generator [1], has a strong theoretical foundation from the computational complexity theory and the number theory. Proofs were given that, under certain reasonable assumptions on which modern cryptography heavily relies, the BBS pseudo-random sequences would pass any feasible statistical test. Unfortunately, the algorithm was found to be too slow for computer simulation applications. In this article, we present a practical implementation of the "x² mod N" generator. We show a variant of the Montgomery modular multiplication algorithm [2] tailored to the typical computer environment used for computer simulations. We observed an adequate level of performance for the "x² mod N" generator to be seriously considered whenever an otherwise "good" pseudo-random generator casts a doubt about the results of a sensitive simulation.
[1] Blum, Leonore, Blum, Manuel, and Shub, M., A Simple Unpredictable Pseudo-random Number Generator, SIAM Journal of Computing, vol. 15, no. 2, May 1986, pp 364-383
[2] Montgomery, Peter L., Modular Multiplication Without Trial Division, Mathemetics of computations, Vol. 44, no. 170, April 1985, pp 519-522
The full text of the article is available in .pdf format. A sample list of 1449 prime numbers of a special form is also available.
See pseudo-random number generators for background information.
CONNOTECH Experts-conseils Inc.
9130 Place de Montgolfier
Montréal, Québec, Canada, H2M 2A1
Tél.: +1-514-385-5691
Fax: +1-514-385-5900