= Solution
The fact that a nontrivial factor usually appears before a full return does not say that either event appears soon. Each iteration of the <RSA cycling attack> is inexpensive, but the number of iterations can be enormous. The <multiplicative orders> governing returns modulo $p$ and $q$ need not be small, and writing down a large return exponent does not provide a fast way to search the preceding iterations.
If this procedure factored arbitrary well-generated <RSA cryptosystem> moduli in feasible time with substantial success, it would solve the associated <integer factorization> problem efficiently. If it instead rapidly returned the predecessor of a <ciphertext> without factoring, it would solve the <RSA inversion problem>. Both are intended to be infeasible for appropriate parameters. Efficient <integer factorization> certainly breaks <RSA cryptosystem> security; the reverse implication for general <RSA inversion problem> algorithms is not known.
$$
\boxed{\text{A likely factor before a return does not establish a feasible running time.}}
$$
Thus the stated observation alone provides no serious general attack on well-generated parameters. It also does not prove a lower bound: special moduli or messages with short cycles can be weak, and the hardness claims are computational assumptions.
Back to article page
