This answer covers use and implementation of the Euclidean algorithm in RSA, first straight for computing the Greatest Common Divisor of two integers; then (half-)extended for the computation of modular inverses.
The (straight) Euclidean algorithm is often used at one step in RSA: when it comes to choose odd $e>1$ and distinct primes $p$ and $q$ such that $\gcd(p-1,e)=1=\gcd(q-1,e)$. It has very little cost compared to other computations involved in that choice, in particular the test that $p$ and $q$ are prime (which is not performed using the Euclidean Algorithm). $e$ is usually small, thus only the first step of the algorithm needs to be carried with large numbers. Further, often $e$ is prime (including when $e=F_k=2^{(2^k)}+1$ with $0\le k\le 4$, the 5 Fermat primes); hence $\gcd(p-1,e)=1$ holds precisely when $p\bmod e\not=1$, and this simple test sidesteps explicit GCD computation.
Another possible use of the (straight) Euclidean algorithm in RSA is when computing $\lambda(N)=(p-1)(q-1)/\gcd(p-1,q-1)$ , if that's desired.
One possible efficient form of the Euclidean algorithm to compute $\gcd(a,b)$ for positive integers $a$ and $b$ repeats (until the algorithm stops):
- $a\gets a\bmod b$ .
That is, replace $a$ with $a'$ matching $0\le a'<b$ and $b$ divides $a-a'$ .
Or equivalently, $q\gets\lfloor a/b\rfloor$ followed by $a\gets a-q\,b$ .
- If $a=0$, then output $b$ and stop.
- Exchange $a$ and $b$ .
Practical implementations often replace the exchange with a copy of the other steps with permutation of $a$ and $b$ .
The average number of steps is significantly reduced in this optimized version, but each step is slightly more complex:
- $q\gets\lfloor(a+b/2)/b\rfloor$ (that is $a/b$ rounded to nearest, sometime noted $\lfloor a/b\rceil$ )
- $a\gets|a-q\,b|$ .
- If $a=0$, then output $b$ and stop.
- Exchange $a$ and $b$ .
In RSA, the extended Euclidean algorithm is often used to compute one or more of the following modular inverses:
- $d=e^{-1}\bmod\varphi(N)\;$ with $\varphi(N)=(p-1)(q-1)$ .
- $d=e^{-1}\bmod\lambda(N)\;$ with $\lambda(N)=(p-1)(q-1)/\gcd(p-1,q-1)$ .
- $d_p=e^{-1}\bmod(p-1)$ .
- $d_q=e^{-1}\bmod(q-1)$ .
- $q_\text{inv}=q^{-1}\bmod p$ .
The last three are used by optimized implementations using the Chinese Remainder Theorem. One of the first two is customary in introductory material on RSA, and useful in practice when $d$ is required (for archival/interchange, or because the CRT optimization is not used).
In all cases, the half-extended Euclidean algorithm can be used to efficiently compute $a^{-1}\bmod b$ for non-negative integer $a$ and positive integer $b$ , manipulating non-negative integers only:
- $x\gets0$ and $y\gets1$ and $m\gets b$ .
Note: $ax+by=m$ will keep holding, with $m$ the original modulus.
- if $a=1$, then output "the desired inverse is $y$" and stop.
- If $a=0$, then output "the desired inverse does not exists" and stop.
- $q\gets\lfloor b/a\rfloor$ .
- $b\gets b-aq$ and $x\gets x+qy$ .
- if $b=1$, then output "the desired inverse is $m-x$" and stop.
- If $b=0$, then output "the desired inverse does not exists" and stop.
- $q\gets\lfloor a/b\rfloor$ .
- $a\gets a-bq$ and $y\gets y+qx$ .
- Continue at 2.
Note: $a$ and $b$ evolve as in the straight Euclidean algorithm; $x$ and $y$ are the (half) extension. The (full) extended Euclidean algorithm keeps two more variables, in order to fully solve the Bezout identity.
Various optimizations apply to the Euclidean algorithm and its (half)-extended variant:
- The quotient $q$ needs not be computed exactly. If it is too small, the penalty is that the next $q$ will be 0. If $q$ is too large, numbers can get negative (and that can be either dealt with, or corrected). We can thus get away with a rough estimation of $q$ (and it pays to round to nearest if we can deal with that).
- Usually, $q$ is small. When the numbers handled use multiple limbs/digits, it pays to optimize the case when $q$ fits a single limb. It may even pay to special-case $q=1$ and $q=2$.
- Large $q$ need to be handled (otherwise worst case execution time becomes linear with the inputs), but is infrequent thus not critical. We can round large $q$ down to a power of two. In fact, restricting to $q$ a power of two is not disastrous, and has the advantage of replacing multiplication with shifts.
- Usually, it is possible to predict the next few values of the (small) $q$ from the high-order bits of $a$ and $b$. That allows to group several transformations of $a$, $b$, $x$, $y$ into linear transformations with moderate multipliers computed from the predicted values of the $q$.
Off-topic since strictly speaking that's no longer the Euclidean algorithm: there is a binary GCD algorithm that performs only subtraction, additions, and divisions by 2. It also has an extended version fully solving the Bezout identity (see the Handbook or Applied Cryptography, algorithm 14.61), and a half-extended version specialized towards computing the modular inverse (see the first section of this answer). It can be competitive with the Euclidean algorithm when multiplication is expensive; and the two can be blended.
