Cryptography Reference
In-Depth Information
The Euclidean algorithm works by simply dividing numbers over and over, keeping track of the remainder
each time. In the case of
a
and
p
, we start by dividing
p
by
a
(although it doesn't really matter which we start
with),
p
=
n
0
×
a
+
r
0
where
n
0
is an integer (which we just throw away) and
r
0
is less than
p
and greater than or equal to zero. This
way,
n
is as big an integer as possible. If
r
0
= 0, then the problem is that
p
is divisible by
a
, so
p
isn't prime.
(In the normal version of the algorithm where we want the GCD, we would stop here and return
a
as the GCD,
since it divides both
a
and
p.)
Otherwise, we continue the algorithm by dividing
a
by
r
0
:
a
= n
1
×
r
0
+
r
1
Again,
n
1
is just some integer, and r
1
is the remainder (0 ≤ r
1
< a).
We iteratively repeat this process until at some point we have the last two equations:
r
i
-1
=
n
i
×
r
i
+
r
i
+1
r
i
=
n
i
+2
×
r
i
+1
+ 0
In the normal algorithm, where we want the GCD, we just found it:
r
i
+1
. Since one of our original numbers
was prime, though, then the GCD, and hence
r
i
+1
, should be 1 (otherwise, it wouldn't be a prime number, so
something would be wrong with the number of the implementation of the algorithm).
How, then, do we get the inverse from this mess? Well, we know, from the second to last step of the al-
gorithm, by replacing
r
i
+1
= 1, that
r
i
-1
=
n
i
+1
×
r
i
+ 1
Rewriting this, we have
1 = r
i-1
-
n
i
+1
×
r
i
We can then use the previouse quation in the algorithm,
r
i-2
=
n
i
r
i-1
+
r
i
, to substitute in the above for
r
i:
1 =
r
i
-1
-
n
i
+1
× (
r
i
-2
-
n
i
r
i
-1
) = -
n
i
+1
r
i
-2
+
n
i
+1
n
i
r
i
-1
We then keep repeating the substitutions back up, eventually obtaining an expression for 1 =
a
×
a
-1
-
np.
Let's run through a quick example by computing the inverse of 17 mod 31 using the Euclidean algorithm:
31 = 1 × 17 + 14
17 = 1 × 14 + 3
14 = 4 × 3 + 2
3 = 1 × 2 + 1
2 = 2 × 1 + 0
Just as we stated above, we start with the second to last equation and work our way backward. To make the
work a little easier to follow, we underline the next number to be substituted:
This last equation is of exactly the correct form, revealing that 17
-1
= 11 (mod 31). We can easily multiply
these out to check our answers.
Search WWH ::
Custom Search