= Solution
Avoid constructing the huge <integers> $c^{3^j}$ explicitly. Maintain $a_0=c$ and $a_j=a_{j-1}^3\bmod n$, computing $g_j=\gcd(a_j-c,n)$ after each step.
In case (1), the nontrivial <greatest common divisor> $g_k$ is one of the <prime factors> $p,q$. Divide $n$ by it, compute $d$ with the <extended Euclidean algorithm>, and return $c^d\bmod n$.
In case (2), $a_k=c\pmod n$. The preceding value satisfies $a_{k-1}^3=c\pmod n$. Cubing is a <bijection> on the <residue classes> modulo $n$, so there is only one such cube root, namely the original <plaintext> $m$. Therefore
$$
\boxed{\begin{array}{ll}1<g_k<n:&\text{factor }n\text{ and decrypt};\\g_k=n:&m=a_{k-1}=c^{3^{k-1}}\bmod n.\end{array}}
$$
For $k=1$, the preceding value is $a_0=c$; a fixed point is its own <plaintext>. Keeping the previous iterate makes the recovery immediate once the <RSA cycling attack> succeeds.
Back to article page
