Page 160 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF ( p ) 143

An executable Ada file Euclidean_algorithm_polynomials2.adb,
including Algorithm 6.2, is available at www.arithmetic-circuits.org.
As the degree of a(x) and b(x) must be known at every step, a kind
of normalized representation could be used. Given a polynomial
+
u
e(x) = e x + e x u − 1 . . . + e with e ≠ 0, u ≤ m
u u − 1 0 u
define
+
m
n_e(x) = e(x)x m – u = e x + e x m − 1 . . . + e x m − u , deg_e = u (6.14)
u u − 1 0
so that
e(x) = n_e(x)x deg_e – m (6.15)

where n_e(x) is a polynomial of degree m. Then, according to Eqs.
(6.13) and (6.15),

−1 s – t
−1 s – t
r(x) = a(x) − b(x)a b x = n_a(x)x s – m − n_b(x)x t – m a b x
s t s t
−1
= (n_a(x) − n_b(x)a b )x s – m
s t
that is,
r(x) = n_r(x)x deg_r – m
where n_r(x) = n_a(x) − n_b(x)a b , deg_r = s (6.16)
−1
s t
Actually, n_r(x) is not of degree m and must be normalized. The
following operations must be executed:
deg_r := deg_a;
while n_r(m) = 0 loop
n_r := multiply_by_x(n_r); deg_r := deg_r-1;
end loop;
Initially, a(x) = f(x) so that n_a(x) = f(x) and deg_a = m. The degree
of b(x) = h(x) is smaller than m and a previous normalization step
must be executed.

Algorithm 6.3—Euclidean algorithm, version 3

n_a := f; deg_a := m; n_b := multiply_by_x(h); deg_b :=
m-1; c := zero; d := g;
--previous step:
while n_b(m) = 0 loop
n_b := multiply_by_x(n_b); deg_b := deg_b-1; end loop;
--
while deg_b > 0 loop
dif := deg_a - deg_b; coef := (n_a(m)*invert(n_b(m)))
mod p;