Choose
randomly, for
,
with
.
Choose
randomly. Add the
corresponding to
mod
to obtain a sequence of
bits. Use the first
bits
as output from the generator. The remaining
bits give you a new
,
for which you obtain a new sum.
This generator is more
efficient than the one in section 8.1, since it uses simpler
operations and produces more than one bit of pseudo-random output
per iteration. The paper establishes connections between the
existence of efficient tests (in the sense of section 8.3)
and the average-case difficulty of subset-sum problems.
We will not try to give a precise statement of the result, but will
try to indicate some of the main ideas.
Suppose there were an efficient algorithm which looked at the
and at
and guessed whether
came from a
sum of the
with probability greater than
.
We will
show that such an algorithm could be used to determine whether
came from a sum with probability close to 1.
In the case in which
we show that
can be used to guess, for each
,
whether
is even or odd with probability greater than
.
Theorem 34 can then be used to identify
with probability
close to 1.
To guess the parity of ,
we make a guess
for the
size of this set and choose a random
.
We have
look at
a problem in which
is replaced by
and
is replaced
by
for each
.
If
is a correct guess,
will see a sum of a subset. Otherwise,
will be a random number,
and we assumed
could distinguish between these two possibilities
with probability greater than
.