Page 20 - Hardware Implementation of Finite-Field Arithmetic

Mathematical Backgr ound 3

Then compute

r (0) = q (1)r (1) + r (2)
r (1) = q (2)r (2) + r (3)
r (2) = q (3)r (3) + r (4)
. . .
r(n − 3) = q(n − 2)r (n − 2) + r (n − 1)
r (n − 2) = q (n − 1)r (n − 1) + r (n)
where r (1) > r (2) > . . . > r (n) = 0 and gcd(r (i − 1), r (i )) = gcd(r (i ),
r (i + 1)), so that

gcd (x, y) = gcd (r (0), r (1)) = . . . = gcd (r (n − 1), r (n)) = gcd(r (n − 1), 0)
= r (n − 1)

Example 1.2 Let r (0) = x = 9520; r (1) = y = 3120;

9520 = 3.3120 + 160
3120 = 19.160 + 80
160 = 2.80 + 0

Then gcd(9520, 3120) = 80.
In the extended Euclidean algorithm a series of coefficients b(i ) and
c(i ) is calculated in parallel with the computation of r (0), r (1),
r (2), . . . , r (n):

b(0) = 1 c(0) = 0
b(1) = 0 c(1) = 1
b(2) = b(0) − b(1)q (1) c(2) = c(0) − c(1)q (1)
. . .
b(n − 1) = b(n − 3) − b(n − 2)q (n − 2) c(n − 1) = c(n − 3) − c(n − 2)
q (n − 2)
It can be demonstrated by induction that

r (i ) = b(i )x + c(i )y ∀ i = 0, 1, 2, . . . , n − 1
In particular

gcd(x, y) = r (n − 1) = b(n − 1)x + c(n − 1)y
In conclusion the extended Euclidean algorithm expresses the
greatest common divisor z of two natural numbers x and y as a linear

combination of x and y, that is,
z = bx + cy (1.1)