[proofplan] The equivalence has two directions. The forward direction is the standard RSA key-generation procedure: given $p$ and $q$, one computes $\phi(N) = (p-1)(q-1)$ and inverts $e$ modulo $\phi(N)$ via the extended Euclidean algorithm. The reverse direction exploits the fact that once $d$ is known, the quantity $m := de - 1$ is a positive multiple of $\phi(N)$, so it fits the hypotheses of the [Factoring from a Multiple of the Totient](/theorems/???) theorem: writing $m = 2^a b$ with $b$ odd, a random $x \in (\mathbb{Z}/N\mathbb{Z})^\times$ exposes a non-trivial square root of $1$ modulo $N$ with probability at least $1/2$, so $r$ independent draws succeed except with probability $2^{-r}$. [/proofplan] [step:Derive the private key from a factorisation of $N$] Suppose an algorithm $\mathcal{A}$ produces the factorisation $N = pq$ in polynomial time. We construct an algorithm $\mathcal{B}$ for the private exponent as follows. Compute \begin{align*} \phi(N) = (p - 1)(q - 1). \end{align*} Since $\gcd(e, \phi(N)) = 1$ by the RSA key-generation assumption, the extended Euclidean algorithm produces integers $d, k$ with \begin{align*} de + k \phi(N) = 1, \end{align*} so $de \equiv 1 \pmod{\phi(N)}$. Reducing $d$ modulo $\phi(N)$ yields the unique residue class of the private exponent. All three operations — subtraction of two $O(\log N)$-bit integers, multiplication, and the extended Euclidean algorithm — run in polynomial time in $\log N$. Hence $\mathcal{B}$ runs in polynomial time. [/step] [step:Reduce factoring $N$ to knowledge of $d$ via the multiple-of-totient extractor] Suppose an algorithm $\mathcal{A}'$ produces $d \in \mathbb{Z}$ with $de \equiv 1 \pmod{\phi(N)}$ from $(N, e)$ in polynomial time. By definition there exists $k \in \mathbb{Z}$ with \begin{align*} de - 1 = k \phi(N). \end{align*} Since $d, e \ge 1$ and $de \ge 1$, the integer $m := de - 1$ is a non-negative multiple of $\phi(N)$. We may assume $m > 0$: the case $m = 0$ forces $de = 1$, so $e = d = 1$, which is excluded by the requirement $\gcd(e, \phi(N)) = 1$ together with $\phi(N) > 1$ unless $e \ne 1$ — and in the degenerate case $e = 1$ the scheme is vacuous and $N$ is not given to be factored under it. For any non-degenerate RSA instance $m > 0$. Write $m = 2^a b$ with $a \ge 1$ and $b$ odd; this decomposition is computed by counting trailing zeros of the binary expansion of $m$, which takes time $O(\log m) = O(\log N)$. [guided] The computation hinges on the identity $m = de - 1 \equiv 0 \pmod{\phi(N)}$. Why does this follow from the definition of $d$? Because $d$ is defined modulo $\phi(N)$ as the inverse of $e$, meaning $de \equiv 1 \pmod{\phi(N)}$, i.e., $\phi(N) \mid de - 1$. So any candidate $d$ satisfying $de \equiv 1 \pmod{\phi(N)}$ produces $m = de - 1$ divisible by $\phi(N)$. Why is $a \ge 1$, i.e., why is $m$ even? Because $\phi(N) = (p-1)(q-1)$ with $p, q$ odd primes greater than $2$, so both $p - 1$ and $q - 1$ are even, and $4 \mid \phi(N) \mid m$. This is exactly the hypothesis of the multiple-of-totient factoring theorem: $a \ge 2$ in fact, though we only need $a \ge 1$ to apply the extractor. (For $p = 2$ or $q = 2$ the RSA problem is trivial, so the relevant case is $p, q$ odd.) [/guided] [/step] [step:Apply the multiple-of-totient factoring theorem with $r$ random witnesses] With $m = 2^a b$ in hand, we invoke the [Factoring from a Multiple of the Totient](/theorems/???) theorem, whose hypothesis is precisely: $N = pq$ with $p, q$ distinct odd primes, and $m$ a positive multiple of $\phi(N)$ with $m = 2^a b$, $b$ odd, $a \ge 1$. Both hypotheses are verified: $N = pq$ is the RSA modulus by construction, and $m = de - 1$ is a multiple of $\phi(N)$ by the previous step, with $a \ge 1$ since $4 \mid \phi(N) \mid m$. The theorem states: for $x$ chosen uniformly at random from $(\mathbb{Z}/N\mathbb{Z})^\times$, the algorithm \begin{align*} &\text{compute } y_0 := x^b \bmod N, \\ &\text{for } i = 1, \dots, a: \; y_i := y_{i-1}^2 \bmod N, \\ &\text{if any } y_i = 1 \text{ with } y_{i-1} \ne \pm 1, \text{ return } \gcd(y_{i-1} - 1, N) \end{align*} produces a non-trivial factor of $N$ with probability at least $1/2$ over the choice of $x$. Our extractor runs this procedure for $r$ independent draws $x_1, \dots, x_r$ from $(\mathbb{Z}/N\mathbb{Z})^\times$. (Drawing uniformly from $(\mathbb{Z}/N\mathbb{Z})^\times$ is done by drawing uniformly from $\{1, \dots, N - 1\}$ and rejecting if $\gcd(x, N) > 1$; since $|(\mathbb{Z}/N\mathbb{Z})^\times| = \phi(N) \ge N - p - q + 1$ and $p, q \le \sqrt{N}$ are both large, rejection occurs with negligible probability and in fact exposes a factor of $N$ directly.) [guided] Why does the multiple-of-totient theorem apply? Its statement requires a positive integer $m$ divisible by $\phi(N)$ with $m = 2^a b$, $b$ odd, $a \ge 1$, and an RSA-style $N = pq$ with distinct odd primes. We have: - $N = pq$ with $p, q$ distinct odd primes — this is the RSA key-generation assumption. - $m := de - 1 > 0$ and $\phi(N) \mid m$ — verified in the previous step. - $m = 2^a b$ with $b$ odd, $a \ge 1$ — any positive even integer has such a decomposition, and $m$ is even because $4 \mid \phi(N) \mid m$. Each hypothesis is verified, so the theorem fires. The probability bound arises as follows. The multiple-of-totient theorem guarantees that a single random $x$ succeeds with probability at least $1/2$. The $r$ draws are independent, so the probability that **all $r$ draws fail** is at most $(1/2)^r = 2^{-r}$. Therefore the probability that **at least one draw succeeds**, and hence that we obtain a non-trivial factor, is at least $1 - 2^{-r}$. The running time is the product of $r$ and the cost of each individual trial. A single trial performs $a + 1$ modular squarings (each $O((\log N)^2)$ by schoolbook multiplication or $O((\log N) \log \log N)$ by fast multiplication) and one $\gcd$ computation ($O((\log N)^2)$). Since $a \le \log_2 m \le \log_2(de) \le 2 \log_2 N$ is itself $O(\log N)$, each trial runs in polynomial time, and $r$ trials together remain polynomial provided $r$ is chosen polynomially in $\log N$. Taking $r = \log_2 N$ gives success probability at least $1 - 1/N$ in time polynomial in $\log N$. [/guided] [/step] [step:Combine the two directions to conclude computational equivalence] The two directions together prove the equivalence. Step 1 converts a factoring oracle into a private-key oracle deterministically and in polynomial time; this is already the RSA key-generation procedure. Step 2 together with Step 3 converts a private-key oracle into a factoring algorithm that succeeds with probability at least $1 - 2^{-r}$ in time polynomial in $\log N$ and $r$. Since each direction is a polynomial-time probabilistic reduction and the error probability $2^{-r}$ in the reverse direction is driven to zero by polynomial increase of $r$, recovering $d$ from $(N, e)$ is computationally equivalent to factoring $N$. This completes the proof. [/step]