Cryptography Reference
In-Depth Information
b
=
r 1 q 2 + r 2
r 1
=
r 2 q 3 + r 3
...
r k− 3
=
r k− 2 q k− 1 + r k− 1
r k− 2
=
r k− 1 q k + r k
All quotients and remainders are integers. At the end, r k is equal to zero
and q 1 ,q 2 ,...,q k ,r 1 ,r 2 ,...,r k− 1 are nonzero. If r k =0, then the last equation
implies that r k− 1 divides r k− 2 . The last-but-one equation implies that it also divides
r k− 3 . This line of argumentation can be continued until the first equation, and hence
r k− 1
divides a and b . None of the other remainders r k− 2 ,r k− 3 ,...,r 1
has this
property. 15 Consequently, r k− 1
is the greatest common divisor of a and b , meaning
that r k− 1 = gcd ( a, b ).
Algorithm 3.1
The Euclidean algorithm to compute the greatest common divisor of a and b .
( a, b ∈ Z , |a|≥|b|,a =0)
a ←|a|
b ←|b|
while b =0do
t ← a
a ← b
b ← t mod b
return a
( gcd ( a, b ))
The Euclidean algorithm is illustrated in Algorithm 3.1. It takes as input two
integers a and b with
=0, and computes as output gcd ( a, b ).
First it replaces a and b with their absolute values (note that this does not change
the greatest common divisor). Then the previously mentioned rule that gcd ( a, b )=
gcd ( b, a mod b ) is applied until b reaches zero. At this point in time, a represents
the greatest common divisor and is returned by the algorithm. Note that the loop can
also be represented by a recursive function call.
The Euclidean algorithm explained so far can be used to compute the greatest
common divisor of two integers a and b . During its execution, all intermediate results
(in particular all quotients q i and remainders r i ) are discarded. This makes the
algorithm simple to implement in the first place. If, however, one does not throw
all intermediate results away but accumulates them during the execution of the
|
a
|≥|
b
|
and a
That's why they are called remainders in the first place (not divisors). Only r k− 1 is a divisor in the
last equation.
15
Search WWH ::




Custom Search