TAOCP 4.5.4 Exercise 13

Section 4.5.4: Factoring into Primes

Exercise 13. [HM25] (J. D. Dixon.) Prove that whenever the algorithm of exercise 12 is pre- sented with a solution $(x,e_0,\ldots,e_m)$ whose exponents are linearly dependent modulo 2

on the exponents of previous solutions, the probability is $2^{1-d}$ that a factorization will not be found, when $N$ has $d$ distinct prime factors and $x$ is chosen at random.

Verified: no
Solve time: 53m27s

Let (N) be an integer with (d) distinct prime factors. (If (N) is even, the power of (2) is removed beforehand; the argument for the odd part is identical and the probability remains (2^{1-d}) where (d) is the number of distinct odd prime factors.) The algorithm of Exercise 12 uses a fixed factor base consisting of primes (p_0, p_1, \ldots, p_m) (and possibly (-1) for the sign) none of which divide (N). A solution is a pair ((x, e_0, \ldots, e_m)) satisfying [ x^2 \equiv \prod_{j=0}^m p_j^{e_j} \pmod N . ] The exponent vector (\mathbf{v} = (e_0 \bmod 2, \ldots, e_m \bmod 2)) belongs to (\mathbb{F}_2^{m+1}). The algorithm maintains a set of previously found solutions whose exponent vectors (\mathbf{v}_1, \ldots, \mathbf{v}k) are linearly independent over (\mathbb{F}2). When a new solution ((x, \mathbf{e})) is presented and its vector (\mathbf{v}) lies in the span of (\mathbf{v}1, \ldots, \mathbf{v}k), there is a unique subset (I \subseteq {1,\ldots,k}) such that [ \mathbf{v} = \sum{i \in I} \mathbf{v}i \pmod 2 . ] The algorithm then forms [ X = x \prod{i \in I} x_i \pmod N, \qquad Y = \prod{j=0}^m p_j^{(e_j + \sum{i \in I} e{ij})/2} \pmod N . ] Because (\mathbf{v}) is the sum of the (\mathbf{v}i), the exponents in (Y) are integers. By construction [ X^2 \equiv Y^2 \pmod N . ] Since the factor base primes are coprime to (N), (\gcd(Y,N)=1). Define (C = \prod{i \in I} x_i \pmod N) and set [ K = Y C^{-1} \pmod N . ] Then [ x^2 \equiv (x C)^2 C^{-2} \equiv X^2 C^{-2} \equiv Y^2 C^{-2} \equiv K^2 \pmod N . ] The congruence (x^2 \equiv K^2 \pmod N) means that the integers (x^2 \bmod N) and (K^2 \bmod N) (both taken in ([0,N-1])) are equal. The new solution ((x, \mathbf{e})) was obtained because (x^2 \bmod N) factors completely over the factor base; therefore (K^2 \bmod N) also factors completely over the factor base, and the same holds for every integer (x') satisfying (x'^2 \equiv K^2 \pmod N). Hence all (2^d) solutions of (x^2 \equiv K^2 \pmod N) are valid solutions in the algorithm’s sense.

The algorithm chooses (x) at random. Given that we have a solution that is linearly dependent with the specific combination (I), the conditional distribution of (x) is uniform over the set of all solutions that satisfy this condition. Because all (2^d) solutions of (x^2 \equiv K^2 \pmod N) satisfy it, (x) is uniformly distributed among these (2^d) residues modulo (N).

Now define (Z = X Y^{-1} \pmod N). Using (K = Y C^{-1}) we have [ Z = X Y^{-1} = x C Y^{-1} = x K^{-1} \pmod N . ] Multiplication by (K^{-1}) is a bijection between the set of solutions of (x^2 \equiv K^2 \pmod N) and the set of solutions of (Z^2 \equiv 1 \pmod N). Since (N) is odd and has (d) distinct prime factors, the Chinese Remainder Theorem shows that (Z^2 \equiv 1 \pmod N) has exactly (2^d) solutions: for each prime power (p^e \parallel N) the equation has the two solutions (Z \equiv \pm 1 \pmod{p^e}), and they combine independently. Therefore (Z) is uniformly distributed over these (2^d) square roots of (1) modulo (N).

The algorithm computes (g = \gcd(X-Y, N)). Because (\gcd(Y,N)=1), [ g = \gcd(Y(Z-1), N) = \gcd(Z-1, N). ] If (Z \equiv 1 \pmod N) then (g = N); if (Z \equiv -1 \pmod N) then (g = 1) (since (N) is odd). In all other cases (Z) is congruent to (1) modulo a proper nonempty subset of the prime power factors of (N) and to (-1) modulo the rest, so (g) is a nontrivial factor of (N). Thus the algorithm fails to find a factor exactly when (Z \equiv \pm 1 \pmod N).

Because (Z) is uniform over the (2^d) solutions of (Z^2 \equiv 1 \pmod N), the probability of failure is [ \frac{2}{2^d} = 2^{1-d}. ]

∎