Portal de Periódicos da CAPES

Efficient, perfect polynomial random number generators

1991; Springer Science+Business Media; Volume: 3; Issue: 3 Linguagem: Inglês

10.1007/bf00196909

1432-1378

Silvio Micali, C. P. Schnorr,

Cryptography and Residue Arithmetic

Let N be a positive integer and let P ε ℤ [x] be a polynomial that is nonlinear on the set ℤ N of integers modulo N. If, by choosing x at random in an initial segment of ℤ N , P(x) (mod N) appears to be uniformly distributed in ℤ N to any polynomial-time observer, then it is possible to construct very efficient pseudorandom number generators that pass any polynomial-time statistical test. We analyse this generator from two points of view. A complexity theoretic analysis relates the perfectness of the generator to the security of the RSA-scheme. A statistical analysis proves that the least-significant bits of P(x) (mod N) are statistically random.