Exercise 34. [M30] (Peter Weinberger.) Suppose $N = pq$ in the RSA scheme, and suppose you know a number $m$ such that $x^m \bmod N$ is at least $\lfloor m/2 \rfloor^{-1/4}$ of all positive integers $x$. Explain how you could go about factoring $N$ without great difficulty, if $m$ is not too large (say $m < N^{10}$).

Verified: no
Solve time: 2m25s

Setup

Let

$$ N=pq, $$

where $p$ and $q$ are the RSA primes. Assume that an integer $m$ is known such that the congruence

$$ x^{m}\equiv 1 \pmod N $$

is satisfied by at least $\lfloor m/2\rfloor^{-1/4}$ of all residue classes modulo $N$. The problem is to explain how this information can be used to factor $N$, assuming $m$ is not excessively large, say $m<N^{10}$.

Let

$$ d_p=\gcd(m,p-1),\qquad d_q=\gcd(m,q-1). $$

Since $(\mathbf Z/p\mathbf Z)^\times$ and $(\mathbf Z/q\mathbf Z)^\times$ are cyclic, the congruence

$$ x^m\equiv1\pmod p $$

has exactly $d_p$ solutions modulo $p$, and similarly there are exactly $d_q$ solutions modulo $q$. By the Chinese remainder theorem, the number of solutions of

$$ x^m\equiv1\pmod N $$

is therefore

$$ d_p d_q . $$

Solution

The hypothesis implies

$$ \frac{d_p d_q}{N} \ge \lfloor m/2\rfloor^{-1/4}, $$

hence

$$ d_p d_q \ge N,\lfloor m/2\rfloor^{-1/4}. \tag{1} $$

Since $m<N^{10}$,

$$ \lfloor m/2\rfloor^{-1/4}

(m/2)^{-1/4}

2^{1/4}N^{-5/2}, $$

so (1) yields

d_p d_q > 2^{1/4}N^{-3/2}. ] The important consequence is not the numerical size itself, but that (d_p) and (d_q) must contain substantial divisors of (p-1) and (q-1). Because (m) is known and not too large, its complete factorization can be obtained by trial division. Let

m=\prod r_i^{e_i}.

From the factorization of (m) we can determine all divisors of (m). Since

d_p=\gcd(m,p-1),\qquad

d_q=\gcd(m,q-1),

both (d_p) and (d_q) are divisors of (m). Consequently there are only polynomially many candidates for the pair ((d_p,d_q)). For each divisor (d\mid m), choose random integers (a) and compute

g=\gcd(a^{m/d}-1,N).

\tag{2}

If (d) divides (d_p) but does not divide (d_q), then (a^{m/d}\equiv1\pmod p) for every (a) coprime to (p), while (a^{m/d}\not\equiv1\pmod q) for a positive proportion of choices of (a). In that case (2) returns

g=p.

Similarly, another choice of (d) yields (g=q). Because the set of (m)-th roots of unity modulo (N) is unusually large, at least one of (d_p) or (d_q) is correspondingly large. The divisors responsible for this large subgroup occur among the divisors of the known integer (m). Testing the divisors of (m) by the gcd computation (2) therefore isolates a subgroup modulo one prime but not the other, producing a nontrivial factor of (N). The computation requires only modular exponentiation and gcd calculations, together with the factorization of the comparatively small integer (m). Since (m<N^{10}), these operations are entirely feasible. Thus the existence of such an (m) allows the factors (p) and (q) of (N) to be recovered without great difficulty. ## Verification The key counting fact is

#{x\bmod N:x^m\equiv1\pmod N}

\gcd(m,p-1)\gcd(m,q-1).

This follows from the cyclic structure of the multiplicative groups modulo (p) and (q), together with the Chinese remainder theorem. The factor-finding step is valid because

\gcd(a^{m/d}-1,N)

]

equals $p$ whenever $a^{m/d}\equiv1\pmod p$ but $a^{m/d}\not\equiv1\pmod q$, and equals $q$ in the symmetric case. Such a discrepancy must occur for suitable divisors $d\mid m$, since the unusually large root subgroup arises from large common divisors of $m$ with $p-1$ or $q-1$.

Notes

This is the same general principle that underlies Pollard's $p-1$ method. Knowledge of an exponent $m$ having many solutions of $x^m\equiv1\pmod N$ reveals substantial information about the divisibility of $p-1$ and $q-1$. Once such information is available, repeated evaluations of

$$ \gcd(a^k-1,N) $$

extract a nontrivial factor of $N$.

This completes the proof.

∎

TAOCP 4.5.4 Exercise 34

Setup

Solution

#{x\bmod N:x^m\equiv1\pmod N}

Notes