# Factorization of RSA modulus using a qubic residue

Suppose that someone uses RSA with $n = pq$, exponent $3$, also $3$ divides $\varphi(n) = (p-1)(q-1)$ and $2$ different roots $y$ and $z$ of the equation:

$$x \equiv c \ (mod \ n)$$

are known (for some qubic residue $c$).

Then can $p$ and $q$ be effectively calculated using $y$ and $z$ and how ? Thanks in advance !

• If $y^3 \equiv c \pmod n$ and $z^3 \equiv c \pmod n$ then $\gcd(y-z,n)$ should give a factor of $n$. – user94293 May 31 '16 at 2:34
• If the public exponent divides $(p−1)(q−1)$, then there is no well-defined private key, and that's not RSA. – fgrieu May 31 '16 at 7:53
• @user94293 I am not sure that this is true if $c$ has more than $3$ qubic roots $(\mod n)$. Can you explain more precisely ? – brick May 31 '16 at 10:15

Let $n = pq$. By assumption, $3$ divides $\varphi(n) = (p-1)(q-1)$. Without loss of generality, I assume that $3$ divides $(p-1)$ or, equivalently, that $p \equiv 1 \pmod {3}$.

Fact Let $p$ be a prime such that $p \equiv 1 \pmod 3$. Let also $c$ be a cubic residue modulo $p$. If $y$ is a cubic root of $c$ then so are $y\cdot \omega \pmod p$ and $y \cdot \omega^2 \pmod p$, where $\omega$ is a non-trivial root of unity modulo $p$ (i.e., $\omega$ satisfies the equation $\omega^2 + \omega + 1 = 0 \pmod {p}$).

In your case, given $c \in \mathbb{Z}_n^*$, you know that $y$ and $z$ are two (distinct) cubic roots of $c$ modulo $n$. Namely, $y^3 \equiv z^3 \equiv c \pmod n$. In turn, this implies $y^3 - z^3 \equiv 0 \pmod n$ and thus $(y-z)(y^2+yz+z^2) \equiv 0 \pmod n$. Since $n = pq$, it follows that

• $(y-z)(y^2+yz+z^2) \equiv 0 \pmod p$, and

• $(y-z)(y^2+yz+z^2) \equiv 0 \pmod q$.

Subcase 1 Assume $q \equiv 2 \pmod 3$ —in this case, cubic roots modulo $q$ are unique. This implies that $y \equiv z \pmod q$. But you cannot have then $y \equiv z \pmod p$ because otherwise you would have $y = z \pmod {n}$ (and $y$ and $z$ are supposed to be distinct). Therefore, since $y \equiv z \pmod q$ yields $(y-z) \equiv 0 \pmod q$ and $y \not\equiv z \pmod p$ yields $(y-z) \not\equiv 0 \pmod p$, you get $\gcd(y-z,n) = q$.

Subcase 2 Assume now $q \equiv 1 \pmod 3$. In this case, there is no guarantee that $\gcd(y-z, n)$ will reveal a factor of $n$. Indeed, it may be the case that, even if $y \neq z \pmod n$, $y^2 + yz + z^2 \equiv 0 \pmod p$ and $y^2 + yz + z^2 \equiv 0 \pmod q$. But you can always give it a try...

• Thanks for answer! One more question: if $gcd(y - z, n) = 1$, then $y^2z$, $yz^2$ and $x$ are $3$ different qubic roots of $x^3$, but this is again not enough to factorize $n$. However if somehow $4$ qubic roots of some element can be constructed $p$ or $q$ can be calculated for sure. So is there some trick to construct $4$ or more different qubic roots from the given two ? – brick May 31 '16 at 16:51
• @brick: It is incorrect to say that $y^2z$ and $yz^2$ are additional cubic roots in this case. – user94293 May 31 '16 at 21:50