Next: The Efficient Test Theorem
Up: Pseudo-random number generators
Previous: The Quadratic Generator
Contents
It would certainly be undesirable if there were an efficient algorithm
which took as input the first bits of the sequence from the generator
and guessed the -st bit with probability much greater than .
We say a generator satisfies the Next Bit Condition if there is
no such algorithm.
Theorem 29
If (QRA) is true, the quadratic generator
satisfies the Next Bit Condition.
Proof: We will show that
an algorithm that could predict the -st bit could be used to
distinguish squares from pseudo-squares mod .
Let . The
sequence of length
can be considered as coming from the quadratic generator with seed the
first term of the sequence. If we take this sequence mod 2 and give
it to our predictor, we would get a guess as to whether
which has probability of being
right. The principle square root of is if is a square,
if is a pseudo-square. Since
mod 2, the
information from the predictor gives us a guess as to whether is
a square.
Next: The Efficient Test Theorem
Up: Pseudo-random number generators
Previous: The Quadratic Generator
Contents
Translated from LaTeX by Scott Sutherland
2002-12-14