Page 31 - Hardware Implementation of Finite-Field Arithmetic

14 Cha pte r O n e

If r ≠ 0, then
0
gcd( g, h) = gcd(r (n − 1), r ) = 1
0
In parallel with the computation of r (0), r (1), r (2), . . . , r (n) two
series of polynomials b(i ) and c(i ) are generated:

b(0) = 1
b(1) = 0
b(2) = b(0) − b(1)q (1), if deg (r (1)) < deg (r (2)) interchange b(1) and b(2)
. . .
b(n − 1) = b(n − 3) − b(n − 2)q (n − 2), if deg (r (n − 2)) < deg (r (n − 1))
interchange b(n − 2) and b(n − 1)
b(n) = b(n − 2) − b(n − 1)q (n − 1)
c(0) = 0
c(1) = 1
c(2) = c(0) − c(1)q (1), if deg (r (1)) < deg (r (2)) interchange c(1) and c(2)
. . .
c(n − 1) = c(n − 3) − c(n − 2)q (n − 2), if deg (r (n − 2)) < deg (r (n − 1))
interchange c(n − 2) and c(n − 1)
c(n) = c(n − 2) − c(n − 1)q (n − 1)
It can be demonstrated by induction that

r (i ) = b(i )g (x) + c(i )h(x), ∀ i = 0, 1, 2, . . . , n
So, if r = 0 then
0
gcd( g, h) = r (n − 1) = b(n − 1)g (x) + c(n − 1)h(x)
and if r ≠ 0, then
0
gcd( g, h) = 1 = r − 1 r (n) = r − 1 b(n)g (x) + r − 1 c(n)h(x)
0 0 0
In the following algorithm u stands for r (i − 1), v for r (i ), r for
r (i + 1), b for b(i − 1), d for b(i ), bb for b(i + 1), c for c(i − 1), e for c(i ), cc
for c(i + 1):

Algorithm 1.2— Variant of the extended Euclidean algorithm for polynomials

u := g; v := h; b := 1; c := 0; d := 0; e := 1;
m := degree(u); t := degree(v);
if t = 0 then
-1
if v(0) = 0 then z = u; else z := 1; b := 0; c := (v(0)) ;
end if;
elsif m = 0 then
if u(0) = 0 then z = v; b := 0; c := 1; else z := 1;
-1
b := (u(0)) ; end if;
else