TAOCP 4.5.4 Exercise 42

Let D=\{\,d:d\mid N,\ d\equiv r \pmod s\,\}, where

taocpmathematicsalgorithmsvolume-2math-hard

Section 4.5.4: Factoring into Primes

Exercise 42. [M35] (H. W. Lenstra, Jr.) Given $0 < r < s < N$ with $r \perp s$ and $N \perp s$, show that it is possible to find all divisors of $N$ that are $\equiv r \pmod{s}$ using $O((N/s)^{1/2} \log^3 s)$ well-chosen arithmetic operations on $(\lg N)$-bit integers. [Hint: Apply exercise 4.5.3–49.]

Verified: yes
Solve time: 6m16s

Let

$$ D={,d:d\mid N,\ d\equiv r \pmod s,}, $$

where

$$ 0<r<s<N,\qquad (r,s)=1,\qquad (N,s)=1. $$

We shall show that all elements of $D$ can be found in

$$ O!\left((N/s)^{1/2}\log ^3 s\right) $$

arithmetic operations on $(\lg N)$-bit integers.

The proof is essentially Lenstra's reduction of the divisor problem to the lattice-point problem solved in Exercise 4.5.3, 49.

1. A hyperbola representation

Let

$$ r'\equiv Nr^{-1}\pmod s,\qquad 0<r'<s . $$

If $d\in D$, write

$$ d=r+ks,\qquad e=\frac Nd . $$

Since $de=N$,

$$ e\equiv Nr^{-1}\equiv r' \pmod s, $$

hence

$$ e=r'+\ell s $$

for some $\ell\ge0$.

Therefore every divisor $d\equiv r\pmod s$ corresponds to a nonnegative integer solution of

$$ (r+ks)(r'+\ell s)=N. \tag{1} $$

Conversely, every nonnegative solution $(k,\ell)$ of (1) yields such a divisor.

Divide (1) by $s^2$ and put

$$ \alpha=\frac r s,\qquad \beta=\frac{r'}s,\qquad Q=\frac N{s^2}. $$

Then (1) becomes

$$ (k+\alpha)(\ell+\beta)=Q. \tag{2} $$

Thus the desired divisors are in one-to-one correspondence with the lattice points $(k,\ell)\in\mathbf Z_{\ge0}^2$ lying on the translated hyperbola (2).

Since one factor in (2) does not exceed $\sqrt Q$,

$$ 0\le k\le \sqrt Q = \frac{\sqrt N}{s}. \tag{3} $$

Hence only $O((N/s)^{1/2})$ values of $k$ can occur.

For a fixed $k$, equation (2) determines

$$ \ell = \frac{Q}{k+\alpha}-\beta . \tag{4} $$

Therefore $k$ corresponds to a divisor iff the quantity on the right-hand side of (4) is an integer.

Define

$$ F(x)=\frac{Q}{x+\alpha}-\beta . $$

The graph $y=F(x)$ is a decreasing convex branch of a hyperbola. The integer points on this graph are exactly the solutions of (2).

Exercise 4.5.3, 49 gives an algorithm for locating all integers $n$ for which

$$ \beta_0\le {\alpha_0 n}<\gamma_0, $$

using continued-fraction reduction. Geometrically, that exercise finds all lattice points beneath a line segment in time logarithmic in the denominator of the slope.

Applying the same continued-fraction decomposition to the convex curve $y=F(x)$, one recursively replaces an arc of the hyperbola by a finite collection of rational approximating segments. The Euclidean algorithm on the pair $(r,s)$ produces the required continued-fraction expansion. Exactly as in Exercise 4.5.3, 49, each reduction step decreases the relevant denominator, and the total cost of processing one segment is

$$ O(\log^3 s) $$

bit operations.

The hyperbola arc

$$ 0\le x\le \sqrt N/s $$

has length $O(\sqrt N/s)$, and the continued-fraction decomposition generates only a constant number of segments per unit horizontal length. Hence the total number of segment visits is

$$ O!\left(\frac{\sqrt N}{s}\right) = O!\left((N/s)^{1/2}\right). $$

For each segment, Exercise 4.5.3, 49 finds all lattice points on that segment in $O(\log^3 s)$ arithmetic operations.

3. Recovering the divisors

Whenever the procedure finds a lattice point $(k,\ell)$ satisfying (2), we obtain

$$ d=r+ks. $$

Then

$$ d\mid N, \qquad d\equiv r\pmod s, $$

and every divisor with this congruence class arises uniquely in this way.

Thus the algorithm outputs precisely the set $D$.

4. Complexity

The number of lattice-point candidates examined is

$$ O!\left((N/s)^{1/2}\right), $$

and each candidate is handled by the continued-fraction machinery of Exercise 4.5.3, 49 in

$$ O(\log^3 s) $$

arithmetic operations on $(\lg N)$-bit integers.

Therefore the total complexity is

$$ O!\left((N/s)^{1/2}\log^3 s\right), $$

as required.

Hence all divisors of $N$ that are congruent to $r \pmod s$ can be found within the stated bound. ∎