Secure Key Exchange over an Insecure Medium with Public Key Cryptography - Implementing SSL/TLS Using Cryptography and PKI - page 137

Computing Modular Inversions with the Extended
Euclidean Algorithm

Although certainly interesting, it's not yet clear how you can use the Euclidean
algorithm to compute the modular inverse of a number as defi ned earlier. The
extended Euclidean algorithm actually runs this same process in reverse, starting
from 0 up to the GCD. It also computes, in the process, two numbers y 1 and y 2
such that ay 1 + zy 2 = gcd(a,z) ; if z is a prime number, y 1 is also the solution
to a 1 a%z 1, which is exactly what you're looking for.

The extended Euclidean algorithm for computing modular inverses is described
algorithmically in FIPS-186-3, Appendix C.1. Listing 3-28 presents it in C code
form.

Listing 3-28: “ecc_int.c” extended Euclidean algorithm (small numbers)

int ext_euclid( int z, int a )
{
int i, j, y2, y1, y, quotient, remainder;

i = a;
j = z;
y2 = 0;
y1 = 1;

while ( j > 0 )
{
quotient = i / j;
remainder = i % j;
y = y2 - ( y1 * quotient );
i = j;
j = remainder;
y2 = y1;
y1 = y;
}
return ( y2 % a );
}

Returning again to the example above of 5 and 6 % 13, remember that

(5 4. ext_euclid tells you what number x satisfied the rela-

tionship (4 x ) % 13

6) % 13

6, thus inverting the multiplication by 5. In this case,

5 and a 13.

z