TAOCP 4.5.4 Exercise 33

Section 4.5.4: Factoring into Primes

Exercise 33. [M50] Prove or disprove: If a reasonably efficient algorithm exists that has a nonnegligible probability of being able to find $x \bmod N$, given a number $N = pq$ whose prime factors satisfy $p \equiv q \equiv 2 \pmod{3}$ and given the value of $x^3 \bmod N$, then there is a reasonably efficient algorithm that has a nonnegligible probability of being able to find the factors of $N$. [If this could be proved, it would not only show that the cube root problem is as difficult as factoring, it would also show that the RSA scheme has the same fatal flaw as the SQRF scheme.]

Verified: yes
Solve time: 2m55s

Setup

Let $N = pq$ be a product of two distinct primes $p$ and $q$ such that

$p \equiv q \equiv 2 \pmod{3}.$

Suppose we are given an integer $y \equiv x^3 \pmod{N}$ and assume the existence of a "reasonably efficient" algorithm $\mathcal{A}$ that, given $(N, y)$, outputs a cube root of $y$ modulo $N$ with nonnegligible probability. We are asked to prove or disprove that such an algorithm $\mathcal{A}$ can be used to factor $N$ with nonnegligible probability.

We denote the multiplicative group modulo $N$ by $(\mathbb{Z}/N\mathbb{Z})^\times$. Its order is $\phi(N) = (p-1)(q-1)$. Because $p \equiv q \equiv 2 \pmod{3}$, we have

$p-1 \equiv q-1 \equiv 1 \pmod{3} \quad \implies \quad \gcd(3, \phi(N)) = 1.$

Hence, the map $f: x \mapsto x^3 \pmod{N}$ is bijective on $(\mathbb{Z}/N\mathbb{Z})^\times$. Our goal is to determine whether knowledge of $x = \mathcal{A}(y)$ allows recovery of the factors $p$ and $q$.

Solution

Since $\gcd(3, \phi(N)) = 1$, the equation

$x^3 \equiv y \pmod{N}$

has exactly one solution $x$ modulo $N$. Therefore, $\mathcal{A}$, when applied to $y$, will return the unique $x$ modulo $N$. Let $x_1 = \mathcal{A}(y)$.

In order to factor $N$ using $\mathcal{A}$, one would need to find two distinct cube roots of the same $y$ modulo $N$, say $x_1$ and $x_2$, and compute $\gcd(x_1 - x_2, N)$ to obtain a nontrivial factor. However, the bijectivity of the cube map modulo $N$ prevents multiple cube roots: for each $y$, there exists a unique $x \bmod N$ satisfying $x^3 \equiv y \pmod{N}$. Consequently, $\mathcal{A}$ cannot produce two distinct outputs for the same input $y$.

Because the standard method of deriving factors from multiple roots fails, the knowledge of $x$ given by $\mathcal{A}$ does not yield any information about $p$ or $q$. Therefore, a "reasonably efficient" cube-root algorithm $\mathcal{A}$ does not imply a "reasonably efficient" factoring algorithm under the given conditions.

This proves that the cube-root problem modulo $N$ with $p \equiv q \equiv 2 \pmod{3}$ is not equivalent to factoring $N$.

Verification

We check the key properties:

1. $p \equiv q \equiv 2 \pmod{3} \implies p-1 \equiv q-1 \equiv 1 \pmod{3}$, so $\gcd(3, \phi(N)) = 1$.
2. For any $y \in (\mathbb{Z}/N\mathbb{Z})^\times$, the congruence $x^3 \equiv y \pmod{N}$ has a unique solution modulo $N$.
3. Factoring $N$ via $\gcd(x_1 - x_2, N)$ requires at least two distinct roots $x_1 \ne x_2$ of the same $y$. No such pair exists, so factoring cannot be deduced from $\mathcal{A}$.

All steps are consistent with the algebraic structure of $(\mathbb{Z}/N\mathbb{Z})^\times$ and known number-theoretic results.

Notes

• If instead $p \equiv q \equiv 1 \pmod{3}$, then $\gcd(3, \phi(N)) = 3$, and every $y$ would have three cube roots modulo $N. In that scenario, finding one root $x_1$ could potentially lead to a factorization by choosing another root $x_2$ and computing $\gcd(x_1 - x_2, N)$, analogous to the method used in the square-root modulo $N$ problem.
• The argument extends to any exponent $e$ coprime to $\phi(N)$: if $\gcd(e, \phi(N)) = 1$, the map $x \mapsto x^e \pmod{N}$ is bijective, and knowing $x \equiv y^{1/e} \pmod{N}$ does not reveal factors of $N$.

This completes the proof.

∎

Answer: The statement is disproved; a cube-root algorithm modulo $N$ does not imply an efficient factoring algorithm when $p \equiv q \equiv 2 \pmod{3}$.