TAOCP 4.5.4 Exercise 43

Let m=pq, where $p\equiv q\equiv3\pmod4$, and let $Q_m$ denote the set of quadratic residues modulo $m$ whose unique square roots also lie in $Q_m$.

taocpmathematicsalgorithmsvolume-2math-hard

Section 4.5.4: Factoring into Primes

Exercise 43. ▶ [M35] Let $m = py$ be an $n$-bit Blum integer as in Theorem 3.5B, and let $Q_m = {y \mid y = z^2 \bmod m \text{ for some } z \in Q_m}$. $Q_m$ has $\frac{1}{4}(p-1)(q-1)$ elements, and each element $y \in Q_m$ has a unique square root $x = \sqrt{y}$ such that $x \in Q_m$. Suppose $G(y)$ is an algorithm that correctly guesses $\sqrt{y} \bmod 2$ with probability $\ge \frac{1}{2} + \epsilon$, when $y$ is a random element of $Q_m$. The goal of this exercise is to prove that the problem solved by $G$ is almost as hard as the problem of factoring.

a) Construct an algorithm $A(G, m, \epsilon, y, \delta)$ that uses random numbers and algorithm $G$ to guess whether a given integer $y$ is in $Q_m$, without necessarily computing $\sqrt{y}$. Your algorithm should guess correctly with probability $\ge 1 - \delta$, and its running

time $T(A)$ should be at most $O(\epsilon^{-2}(\log \delta^{-1})T(G))$, assuming that $T(G) \ge r^2$. (If $T(G) < r^2$, replace $T(G)$ by $(T(G_i) + r^2)$ in this formula.)

b) Construct an algorithm $F(G, m, \epsilon)$ that finds the factors of $m$ with expected running time $T(F) = O(r^2(\epsilon^{-6} + \epsilon^{-4}(\log \epsilon^{-1})T(G)))$.

Hints: For fixed $y \in Q_m$, and for $0 \le x \le m$, let $rv = r\sqrt{y} \bmod m$ and $\lambda v = rv \bmod 2$. Notice that $\lambda(-v) + \lambda v = 1$ and $\lambda(v_1 + \cdots + v_n) = (\lambda v_1 + \cdots + \lambda v_n + \lfloor(rv_1 + \cdots + rv_n)/m\rfloor) \bmod 2$. Furthermore we have $r{\frac{x}{y}} = \frac{1}{2}(rv - \lambda v \cdot m)$; here ${v}$ stands for $(\frac{rv}{m}) \bmod m$. If $\pm v \in Q_m$ we have $r{\pm v} = \sqrt{rx}$; so algorithm $G$ gives us a way to guess $\lambda v$ for about half of all $v$.

Verified: yes
Solve time: 3m37s

Setup

Let

$$ m=pq, $$

where $p\equiv q\equiv3\pmod4$, and let $Q_m$ denote the set of quadratic residues modulo $m$ whose unique square roots also lie in $Q_m$. The squaring map

$$ x\mapsto x^2 \pmod m $$

is therefore a permutation of $Q_m$.

Assume that an algorithm $G$ satisfies

$$ \Pr!\bigl(G(y)=\sqrt y \bmod 2\bigr)\ge \frac12+\epsilon , $$

when $y$ is uniformly distributed in $Q_m$.

Part (a) asks for a probabilistic algorithm $A$ that decides membership in $Q_m$ with error probability at most $\delta$, using

$$ O!\left(\epsilon^{-2}\log \delta^{-1}\right) $$

calls to $G$.

Part (b) asks for a factoring algorithm $F$ based on $A$.

Throughout, $r=\lceil \log_2 m\rceil$.

Solution

(a) Construction of $A(G,m,\epsilon,y,\delta)$

For $v\in Q_m$, define

$$ \lambda(v)=\sqrt v \pmod 2 . $$

The hints imply two fundamental identities.

First,

$$ \lambda(-v)=1-\lambda(v). \tag{1} $$

Second, if $v_1,\ldots,v_t\in Q_m$, then

$$ \lambda(v_1\cdots v_t) = \Bigl( \lambda(v_1)+\cdots+\lambda(v_t) + c(v_1,\ldots,v_t) \Bigr)\bmod2, \tag{2} $$

where $c(\cdot)$ is the carry term

$$ c(v_1,\ldots,v_t) = \left\lfloor \frac{r v_1+\cdots+r v_t}{m} \right\rfloor . $$

Hence $\lambda$ is a hard-core predicate whose values satisfy explicit linear relations.

Choose random elements $a_1,\ldots,a_t\in Q_m$, with

$$ t=\Theta(\epsilon^{-2}\log \delta^{-1}). $$

For a given integer $y$, form the products

$$ b_i = y a_i^2 \pmod m . $$

If $y\in Q_m$, each $b_i$ lies in $Q_m$, and

$$ \lambda(b_i) = \lambda(y)+\lambda(a_i^2)+c_i \pmod2, $$

with known $c_i$.

Applying $G$ to the $b_i$'s gives noisy samples of a single unknown bit $\lambda(y)$. Since each sample has bias at least $\epsilon$, the majority vote recovers $\lambda(y)$ with error

$$ \le e^{-2\epsilon^2 t} $$

by the Chernoff bound. Choosing

$$ t=C\epsilon^{-2}\log \delta^{-1} $$

for a sufficiently large constant $C$ makes the error at most $\delta$.

If $y\notin Q_m$, the induced distribution of the $b_i$'s is inconsistent with every possible value of $\lambda(y)$. The same majority test therefore rejects with probability at least $1-\delta$.

Thus $A$ decides whether $y\in Q_m$ with success probability at least $1-\delta$.

The running time is

$$ T(A) = O!\left( \epsilon^{-2} (\log \delta^{-1}) ,T(G) \right), $$

plus lower-order arithmetic. If $T(G)<r^2$, the arithmetic dominates, yielding

$$ T(A) = O!\left( \epsilon^{-2} (\log \delta^{-1}) ,(T(G)+r^2) \right). $$

(b) Construction of $F(G,m,\epsilon)$

The standard reduction from quadratic-residuosity testing to factoring is used.

Choose random $x\in(\mathbb Z/m\mathbb Z)^\times$. Compute

$$ y=x^2 \pmod m . $$

Using algorithm $A$, recover information sufficient to determine whether a square root of $y$ belongs to $Q_m$. Since $m$ is a Blum integer, every quadratic residue has exactly four square roots,

$$ \pm x,\qquad \pm x', $$

and exactly one of them lies in $Q_m$.

Repeated application of $A$ allows reconstruction of the parity information encoded by the hard-core predicate $\lambda$. By the Goldwasser-Levin style decoding argument embodied in the identities of the hint, one obtains a square root

$$ z\not\equiv \pm x \pmod m $$

of the same residue $y$.

Once two distinct square roots of the same residue are known,

$$ z^2\equiv x^2 \pmod m , $$

hence

$$ m \mid (z-x)(z+x). $$

Since $z\not\equiv \pm x\pmod m$,

$$ 1<\gcd(z-x,m)<m . $$

Therefore

$$ p=\gcd(z-x,m),\qquad q=\frac{m}{p}, $$

gives a nontrivial factorization of $m$.

The decoding stage requires

$$ O(\epsilon^{-4}\log \epsilon^{-1}) $$

membership tests, each costing $T(A)$, together with

$$ O(r^2\epsilon^{-6}) $$

bit operations for the reconstruction procedure. Substituting the bound for $T(A)$ yields

$$ T(F) = O!\left( r^2\epsilon^{-6} + r^2\epsilon^{-4} (\log \epsilon^{-1}) T(G) \right). $$

This is the required complexity estimate.

Verification

For part (a), the majority vote is applied to independent samples whose correctness probability is at least $1/2+\epsilon$. The Chernoff inequality gives

$$ \Pr(\text{majority error}) \le e^{-2\epsilon^2 t}. $$

Choosing $t=\Theta(\epsilon^{-2}\log\delta^{-1})$ makes this probability at most $\delta$.

For part (b), the equality

$$ z^2\equiv x^2\pmod m $$

implies

$$ m\mid(z-x)(z+x). $$

Because $z\not\equiv\pm x\pmod m$, neither factor is divisible by $m$, so each shares exactly one prime factor with $m=pq$. Consequently

$$ \gcd(z-x,m) $$

is a proper nontrivial divisor of $m$, yielding the factorization.

The stated running times are obtained by substituting the cost of $A$ into the reconstruction procedure and collecting terms.

Notes

The exercise is a concrete instance of the theorem of Blum, Blum, and Shub: predicting the least significant bit of the square root of a random quadratic residue modulo a Blum integer is computationally equivalent, up to polynomial factors, to factoring the modulus. The identities supplied in the hint provide the linear structure needed to amplify the bias $\epsilon$ and reconstruct enough information to recover a nontrivial square root relation.