TAOCP 3.5 Exercise 43

Section 3.5: What Is a Random Sequence?

Exercise 43. [26] It seems just as difficult to find the factors of any fixed $R$-bit Blum integer $M$ as to find the factors of a random $R$-bit integer. Why then is Theorem P stated for random $M$ instead of fixed $M$?

Verified: yes
Solve time: 1m48s

Setup

Let Theorem P be the result asserting that a prediction algorithm for the output of the Blum-Blum-Shub generator can be converted into a factoring algorithm for a random $R$-bit Blum integer $M$.

The question asks why the theorem is formulated for random $M$, even though there is strong heuristic evidence that factoring any particular fixed $R$-bit Blum integer is no easier than factoring a randomly chosen one.

The issue is not the presumed difficulty of factoring. The issue is what can actually be proved.

Solution

A theorem must be derived from assumptions that are available in the proof. The proof of Theorem P constructs a factoring procedure whose success probability is measured over the choice of the modulus $M$ and over the auxiliary random choices used by the reduction.

Suppose that an algorithm $A$ predicts the next bit of the generator with nontrivial advantage. The proof analyzes the average behavior of $A$ over all Blum integers of a given size. From this analysis it obtains a factoring algorithm that succeeds for a positive fraction of those integers.

This establishes an average-case statement:

If prediction is possible, then a randomly chosen Blum integer can be factored with nonnegligible probability.

The argument does not identify which individual moduli have the required property. A set of exceptional moduli may exist for which the reduction fails, and the proof provides no mechanism for ruling them out.

To obtain a theorem for a fixed modulus $M$, one would need a much stronger conclusion. One would have to show that, for every Blum integer $M$ of the prescribed size, a successful predictor yields a factoring algorithm for that same modulus. The averaging argument used in the proof does not imply such a statement.

The distinction is the standard difference between average-case and worst-case assertions. From

$$ \Pr_M{\text{factoring algorithm succeeds on }M}\ge \varepsilon $$

one cannot deduce that

$$ \text{the algorithm succeeds on every }M. $$

A simple analogy is that an algorithm may succeed on $90%$ of all inputs while failing on the remaining $10%$; the average success probability gives no information about any particular input lying in the exceptional set.

Therefore Theorem P is stated for random $M$ because that is exactly what the proof establishes. Any stronger theorem for fixed $M$ would require additional arguments that eliminate all exceptional moduli, and no such argument is provided.

Verification

The proof of Theorem P derives a factoring procedure whose probability of success is computed with respect to a distribution on Blum integers. Hence the conclusion concerns randomly selected moduli.

A statement about a fixed modulus would require a bound that holds uniformly for every modulus. Average-case success over a distribution does not imply uniform success on each individual element of the support of that distribution.

Therefore the theorem's formulation matches the strongest result proved.

Notes

The heuristic belief that every fixed $R$-bit Blum integer is essentially as hard to factor as a random one is a conjectural strengthening of the theorem's conclusion. Theorem P avoids such an unproved assumption and restricts itself to the average-case statement that follows rigorously from the reduction.