TAOCP 4.5.4 Exercise 30

Section 4.5.4: Factoring into Primes

Exercise 30. [**] [HM35] (J. D. Dixon and Claus-Peter Schnorr.) Let $p_1 < \cdots < p_m$ be primes that do not divide the odd number $N$, and let $r$ be an even integer $\le \log N / \log p_m$. Prove that the number of integers $X$ in the range $0 \le X < N$ such that $X^2 \bmod N =$

$p_1^{e_1} \cdots p_m^{e_m}$ is at least $nr/r!$. Hint: Let the prime factorization of $N$ be $q_1^{f_1} \cdots q_d^{f_d}$. Show that a sequence of exponents $(e_1, \ldots, e_m)$ leads to $2^d$ solutions $X$ whenever we have $e_1 + \cdots + e_m \le r$ and $p_1^{e_1} \cdots p_m^{e_m}$ is a quadratic residue modulo $q_i$ for $1 \le i \le d$. Such exponent sequences can be obtained as ordered pairs $(e_1', \ldots, e_m'; e_1'', \ldots, e_m'')$ where $e_1' + \cdots + e_m' \le \frac{r}{2}$ and $e_1'' + \cdots + e_m'' \le \frac{r}{2}$ and

$$ (p_1^{e_1'} \cdots p_m^{e_m'})^{(q_i - 1)/2} \equiv (p_1^{e_1''} \cdots p_m^{e_m''})^{(q_i - 1)/2} \pmod{q_i} \quad \text{for} \quad 1 \le i \le d. $$

Verified: yes
Solve time: 2m11s

---

Let

$$ S={(e_1,\ldots,e_m): e_1+\cdots+e_m\le r/2}. $$

By exercise 29,

$$ |S|\ge \frac{m^{r/2}}{(r/2)!}. $$

For each $(e_1,\ldots,e_m)\in S$, define the $d$-tuple

$$ \Bigl(\chi_1,\ldots,\chi_d\Bigr),\qquad \chi_i\equiv \bigl(p_1^{e_1}\cdots p_m^{e_m}\bigr)^{(q_i-1)/2}\pmod{q_i}, $$

whose components are $\pm1$. Since there are only $2^d$ possible such $d$-tuples, at least

$$ \frac{|S|^2}{2^d} $$

ordered pairs

$$ (e_1',\ldots,e_m';,e_1'',\ldots,e_m'') $$

have the same $d$-tuple. For each such pair, put

$$ e_j=e_j'+e_j''. $$

Then $e_1+\cdots+e_m\le r$, and

$$ \bigl(p_1^{e_1}\cdots p_m^{e_m}\bigr)^{(q_i-1)/2}\equiv1\pmod{q_i} \qquad(1\le i\le d), $$

so $p_1^{e_1}\cdots p_m^{e_m}$ is a quadratic residue modulo every $q_i$, hence modulo every $q_i^{f_i}$. Therefore the congruence

$$ X^2\equiv p_1^{e_1}\cdots p_m^{e_m}\pmod N $$

has exactly $2^d$ solutions modulo $N$, by the Chinese remainder theorem. Consequently the total number of integers $X$ with

$$ 0\le X<N,\qquad X^2\bmod N=p_1^{e_1}\cdots p_m^{e_m} $$

for some exponent vector satisfying $e_1+\cdots+e_m\le r$ is at least

$$ 2^d\cdot\frac{|S|^2}{2^d}=|S|^2. $$

Using $|S|\ge m^{r/2}/(r/2)!$ and

$$ \frac1{((r/2)!)^2}\ge \frac1{r!}, $$

we obtain

$$ |S|^2\ge \frac{m^r}{r!}. $$

Hence the number of such integers $X$ is at least

$$ \boxed{\frac{m^r}{r!}}. $$

This completes the proof.

∎