The Euclidean, Extended Euclidean, and RSA Algorithms

The Euclidean Algorithm is a methodical process for calculating the greatest common divisor of two integers. It does not require the factorization of the integers which is an advantage for large integers. The Extended Euclidean Algorithm is a methodical process for finding the integer coefficients in the linear representation of the gcd in terms of the original two integers. The RSA Algorithm is a public key cryptographic system in wide use in computer systems all over the world. The system's security rests on the mathematical fact that there is no known easy way to factor sufficiciently large integers. (If a way was discovered, there would be hell to pay in the world of secure data.) The system includes a so-called public key pair by which messages are encrypted and private key pair by which they are decrypted. When the public key pair is established and published, the privacy key of the private key pair is computed using the Extended Euclidean Algorithm. The paper The Euclidean and RSA Algorithms, gives a detailed description and drivation of the Euclidean Algorithms as well as a description and worked example of the RSA Algorithm.