In cryptographic systems, it is usually necessary to
calculate the inverse of the modulus function of one number to another.
For example xy = 1 mod 317. As expected it can be very
difficult to compute x for any given y.
The Extended Euclidean Algorithm provides an elegant way to
calculate this inverse function. The Algorithm calculates the greatest common
divisor (gcd) of two integers.
y, the inverse of x exists if and only if gcd(x, n) = 1
i.e. , for an integer s, there exists an integer y such that
xy + sn = 1, where y is the inverse of x mod n, also known as the modular
inverse.
To calculate y, using the Extended Euclidean function:
The Extended Euclidean Algorithm for finding the inverse of
a number mod n.
We will number the steps of the Euclidean algorithm starting
with step 0. The quotient obtained at step i will be denoted by qi. As we carry
out each step of the Euclidean algorithm, we will also calculate an auxillary
number, yi. For the first two steps, the value of this number is given: y0 = 0
and y1 = 1. For the remainder of the steps, we recursively calculate yi = yi-2
- yi-1 qi-2 (mod n). Continue this calculation for one step beyond the last
step of the Euclidean algorithm.
The algorithm starts by "dividing" n by x. If the
last non-zero remainder occurs at step k, then if this remainder is 1, x has an
inverse and it is yk+2. (If the remainder is not 1, then x does not have an
inverse.) Here is an example:
Find the inverse of 15 mod 26.
Step 0: 26
= 1(15) + 11 y0 = 0
Step 1: 15
= 1(11) + 4 y1 = 1
Step 2: 11
= 2(4) + 3 y2 = 0 - 1( 1) mod 26 = 25
Step 3: 4 =
1(3) + 1 y3 = 1 - 25( 1) mod 26 = -24
mod 26 = 2
Step 4: 3 =
3(1) + 0 y4 = 25 - 2( 2) mod 26 = 21
y5
= 2 - 21( 1) mod 26 = -19 mod 26 = 7
Notice that 15(7) = 105 = 1 + 4(26) is equivalent to 1 (mod 26).
The Extended Euclidean Algorithm is a gift,
cryptographically speaking, even though it has many more applications
beyond cryptography.
References:
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm http://www.antilles.k12.vi.us/math/cryptotut/extended_euclidean_algorithm.htm