Page 30 - Hardware Implementation of Finite-Field Arithmetic

Mathematical Backgr ound 13

The sequence of operations is almost the same as for computing the
greatest common divisor of two integers. A series of polynomials r (0),
r (1), r (2), . . . are generated. Initially assume that deg ( g) > deg (h) and
define
r (0) = g (x) and r (1) = h(x)

At each step the decomposition [Eq. (1.4)] is used:

u(x) = r (i − 1), v(x) = r (i ), m = deg (r (i − 1)),
t = deg (r (i )), deg (r (i − 1)) > deg (r (i ))

so that
r (i − 1) = q (i )r (i ) + r (i + 1)
where

q (i ) = u (v ) x , r (i + 1) = r (i − 1) − q (i )r (i ),
− 1 m − t
m
t
deg (r (i + 1))< m = deg (r (i − 1))
At the end of the step, r (i ) and r (i + 1) are interchanged if deg (r (i )) <
deg (r (i + 1)).
Operations:
r (0) = g (x)
r (1) = h(x)
r (0) = r (1)q (1) + r (2), if deg (r (1)) < deg (r (2)) interchange r (1) and r (2)
r (1) = r (2)q (2) + r (3), if deg (r (2)) < deg (r (3)) interchange r (2) and r (3)
r (2) = r (3)q (3) + r (4), if deg (r (3)) < deg (r (4)) interchange r (3) and r (4)
. . .
r (n − 3) = r (n − 2)q (n − 2) + r (n − 1), if deg (r (n − 2)) < deg (r (n − 1))
interchange r (n − 2) and r (n − 1)
r (n − 2) = r (n − 1)q (n − 1) + r (n)

where
deg (r (0)) > deg (r (1)) > . . . > deg (r (n)) = 0
and
gcd(r (i ), r (i + 1)) = gcd(r (i + 1), r (i + 2))

so that

gcd( g, h) = gcd(r (0), r (1)) = . . . = gcd(r (n − 1), r (n))
Let r be the coefficient of x in r (n). If r = 0, then
0
0 0
gcd( g, h) = gcd(r (n −1 ), 0) = r (n − 1)