# Is xgcd faster than Fermat for calculating $d$ in RSA?

I want to calculate $d$ from $e$ when generating RSA keys.

What is faster?

• Calculating $\operatorname{xgcd}(e,p)$ and $\operatorname{xgcd}(e,q)$ and CRT.
• Or calculating $e^{p-2}\bmod p$ and $e^{q-2}\bmod q$ and CRT.

I'm having a hard time understanding how to calculate the complexity here.

• Typically, when creating an RSA private/public key pair, almost all the time is taken searching for primes; the tiny amount of time taken computing $d$ (or $dp$ and $dq$) is negligible; either method you cite would work. Dec 11 '14 at 15:35

• The extended Euclidean algorithm ($\operatorname{xgcd}$), when applied to $p$ and $e<p$, uses at most $\lceil\log_\phi(\sqrt5(p+1))\rceil-2\in\mathcal O(\log p)$ divisions in $\mathbb Z$. (This is Knuth's corollary to Lamé's theorem.)
• Using Fermat's little theorem and square-and-multiply exponentiation on $e$ modulo $p$ takes at most $2\cdot\lfloor\log_2(p-2)\rfloor\in\mathcal O(\log p)$ multiplications in $\mathbb F_p$.
Therefore, both methods are asymptotically equivalent. However, there are some practical benefits when using $\operatorname{xgcd}$: