- 1.
- there is an efficient algorithm for deciding whether is true
- 2.
- if we are given , there is no efficient algorithm for guessing whether is true which has a probability much greater than of being right.

where we are looking only at those which are squares.

satisfies the Next Bit Condition.

**Proof:** If there were a program which took as input a se
quence of bits and could guess the next bit, we could get a good
guess on
with
known
by asking the next-bit predictor what would
occur next in the sequence

(this is really the same proof as in the case of the quadratic generator).

- ... function.
^{16} - In later work, we will be defining a one-way function to be such that there is no efficiently computable with for most .

1998-03-15