next up previous contents
Next: Hard-Core Predicates and Pseudo-Random Up: Blair's Cryptography Notes Previous: The Efficient Test Theorem   Contents

Further results on pseudo-random generators

The two main results of the preceding section were the Next Bit Theorem and the Efficient Tests Theorem. The former depended on (QRA) and facts about squares and pseudo-squares. The latter was an abstract result about properties of arbitrary generators. Our first result is an abstract version of the Next Bit Theorem.


Translated from LaTeX by Scott Sutherland