We have seen several functions
with the property that was easy to compute but
was difficult. Such an
is called
a one-way function.16 A predicate
is a property
which is true or false for any .
Typical examples might be ``is an odd number'' or ``is .''
A hard-core predicate for a function
is a predicate
such that
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.
The example we used in the quadratic number generator was
where we are looking only at those
which are squares.
Theorem 32
If
is a hard-core predicate for ,
the random number
generator in which a seed
is chosen at random, giving the
sequence of bits
satisfies the Next Bit Condition.
As a corollary,
the sequence ,
,...satisfies all efficient tests,
using the arguments in the preceding section.
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).