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: Factoring records (currently ~829 bits) give us a lower bound on RSA's security. The actual security might be slightly different — either harder (if e-th roots are harder than factoring) or easier (if there's a shortcut nobody has found).

Go deeper:

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