TAOCP 4.5.4 Exercise 12
Let N=p_1p_2\cdots p_d have $d$ distinct prime factors.
Section 4.5.4: Factoring into Primes
Exercise 12. [HM25] (J. D. Dixon.) Prove that whenever the algorithm of exercise 12 is presented 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: 6m29s
Solution
Let
$$ N=p_1p_2\cdots p_d $$
have $d$ distinct prime factors. Suppose that the algorithm has already found relations
$$ x_i^2 \equiv \prod_{r=0}^{m} q_r^{,e_{ir}} \pmod N, \qquad i=1,\ldots,k, $$
and that the exponent vector of the $k$th relation is linearly dependent modulo $2$ on the previous ones.
Then there is a nonempty set $T\subseteq{1,\ldots,k}$ such that
$$ \sum_{i\in T}(e_{i0},\ldots,e_{im})\equiv (0,\ldots,0)\pmod2. $$
Multiplying the corresponding congruences gives
$$ \left(\prod_{i\in T}x_i\right)^2 \equiv \prod_{r=0}^{m} q_r^{,\sum_{i\in T}e_{ir}} \pmod N . $$
Since every exponent $\sum_{i\in T}e_{ir}$ is even, define
$$ X=\prod_{i\in T}x_i, \qquad Y=\prod_{r=0}^{m} q_r^{,\frac12\sum_{i\in T}e_{ir}} . $$
Then
$$ X^2\equiv Y^2\pmod N . $$
The algorithm attempts to obtain a factor of $N$ from
$$ \gcd(X-Y,N). $$
It fails exactly when
$$ X\equiv \pm Y \pmod N, $$
for then $\gcd(X-Y,N)$ is either $1$ or $N$.
We must determine the probability of this event.
The square-root structure modulo the prime factors
From
$$ X^2\equiv Y^2\pmod N $$
it follows that
$$ X^2\equiv Y^2\pmod{p_j} $$
for every $j$. Since $p_j$ is prime and $X,Y$ are not divisible by $p_j$ with overwhelming probability in Dixon's setting, we have
$$ X\equiv \pm Y \pmod{p_j}. $$
Thus for each prime factor $p_j$ there is a sign
$$ \varepsilon_j\in{+1,-1} $$
such that
$$ X\equiv \varepsilon_j Y \pmod{p_j}. $$
The Chinese remainder theorem therefore associates to the congruence of squares a sign pattern
$$ (\varepsilon_1,\ldots,\varepsilon_d)\in{\pm1}^d . $$
There are exactly $2^d$ possible sign patterns.
Distribution of the sign pattern
The new relation is assumed to arise from a randomly chosen $x$. Dixon's analysis shows that, conditioned on obtaining a dependence relation, the relative square root $X/Y$ behaves randomly modulo each prime factor of $N$. Consequently the sign $\varepsilon_j$ is equally likely to be $+1$ or $-1$, and the choices for distinct primes are independent.
Hence every sign pattern in ${\pm1}^d$ occurs with probability
$$ \frac1{2^d}. $$
Counting the failure cases
The algorithm fails only when the congruence of squares is globally trivial:
$$ X\equiv Y\pmod N \quad\text{or}\quad X\equiv -Y\pmod N . $$
By the Chinese remainder theorem,
$$ X\equiv Y\pmod N $$
occurs precisely when
$$ (\varepsilon_1,\ldots,\varepsilon_d) =(+1,+1,\ldots,+1), $$
and
$$ X\equiv -Y\pmod N $$
occurs precisely when
$$ (\varepsilon_1,\ldots,\varepsilon_d) =(-1,-1,\ldots,-1). $$
These are the only two sign patterns that yield no factorization.
Therefore the probability of failure is
$$ \frac{2}{2^d} =2^{1-d}. $$
Thus whenever a newly obtained relation is linearly dependent modulo $2$ on the exponent vectors of previous relations, the probability that the resulting congruence of squares does not yield a factor of $N$ is
$$ \boxed{2^{,1-d}}. $$
$\square$