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.
The extended Euclidean algorithm ($\operatorname{xgcd}$), when applied to $p$ and $e&lt;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}$:


The involved numbers' bit length decreases very quickly.
A division with remainder is generally cheaper than a multiplication followed by a modulo operation.