RSA ⇔ FAC

Equivalence · free reduction · non-standard model · DLO24

Statement

Against generic ring algorithms, which access ${\mathbb{Z}}_n$ only through ring operations and equality tests, computing $e$-th roots modulo $n$ (RSA) is equivalent to factoring $n$, even when the adversary receives an advice string from unbounded preprocessing on $n$: any such RSA adversary converts into a factoring adversary with polynomially related online complexity and polynomially longer advice — DLO24. The converse holds unconditionally: the factorization of $n$ gives $\varphi (n)$ and hence $d\equiv e^{-1}(\mathrm{mod}\varphi (n))$ — RSA78 (RSA ⇒ FAC). Algorithms that use the bit representation of ring elements are not covered.

Notes

• Without preprocessing, the equivalence is due to AM09.