Efficient, perfect polynomial random number generators

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