True or false: "If you can compute $x = \sqrt[e]{y} \mod N$ ($e$-th root), then you can also factor $N = p \cdot q$."

Not proven! The reverse direction (factoring ⇒ $e$-th root) IS proven, but whether computing $e$-th roots implies you can factor has never been demonstrated.

* Factoring is sufficient to break RSA, but nobody has shown it is necessary — a hypothetical $e$-th-root shortcut could exist without factoring. *

What we know:

• Factoring → $e$-th root: ✓ Proven. If you factor $N = p \cdot q$, you compute $\varphi(N) = (p-1)(q-1)$, then $d = e^{-1} \mod \varphi(N)$, then $x = y^d \mod N$.
• $e$-th root → Factoring: ✗ NOT proven. There might exist a method to compute $e$-th roots without ever learning the factors of $N$.

Why this matters:

• RSA's security is often described as "relying on the hardness of factoring"
• More precisely: RSA relies on the hardness of computing $e$-th roots mod $N$
• Factoring is sufficient to break RSA, but may not be necessary
• If someone found a way to compute $e$-th roots without factoring, RSA would be broken even though factoring remains hard

The practical implication: because factoring breaks RSA, RSA can never be harder to break than factoring $N$. The cost of factoring is therefore an upper bound on the attack effort, and factoring records (currently ~829 bits) tell us which key sizes are definitely too small. RSA could only turn out easier, if someone found an $e$-th-root shortcut that avoids factoring.

Go deeper:

• The RSA problem (Wikipedia) — the open question of whether the RSA problem is equivalent to factoring.