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}
\end{displaymath}

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



 

David J. Wright
2000-09-11