next up previous contents
Next: Integer Division Up: Cryptology Class Notes Previous: Prime Numbers

Euclid's Algorithm

Euclid's algorithm is the most efficient algorithm for finding the greatest common factor of two numbers a and m. If they are relatively prime, which means the greatest common factor is 1, then Euclid's algorithm can also efficiently solve the modular equation

\begin{displaymath}a x \equiv 1 \pmod{m}

for an integer x, which is the modular inverse of a.


David J. Wright