From Euclid's GCD to Montgomery Multiplication to the Great Divide

Euclid's method for finding the greatest common divisor (GCD) of two integers was first described around the year 300 B.C. This simple iterative method is often regarded as the grandfather of all algorithms in Number Theory today. Many advances have been made since then--for example, Berlekamp's algorithm for multiplicative inverse and Montgomery's technique for modular multiplication. These binary add-and-shift algorithms for efficient finite field arithmetic operations have played important roles in today s public-key cryptographic systems.

Yet, two thousand three hundred years after Euclid's GCD, one algorithm remained missing--division. For many decades we did not tackle modular division problems directly. Instead, we relied on the Extended Euclidean algorithm for calculating inversion and we computed division in a two-step process--inversion followed by multiplication. This practice is so deeply rooted in our teachings and doings today that we have neglected to ask whether the idea underlying the binary Extended Euclidean algorithm can also be applied to finding a general solution for field division. This paper describes such a solution: a binary add-and-shift algorithm for modular division in a residue class. This technique for fast computation of divisions in GF(2^m) is the key to a highly efficient implementation of elliptic curve cryptosystems.