Page 159 - Hardware Implementation of Finite-Field Arithmetic

142 Cha pte r S i x

Finally degree(u(x)) = degree(g(x)) + m − degree(r (x)) + degree(r (x)) −
i i − 2 i − 2
degree(r (x)) = degree(g(x)) + m − degree(r (x)).
i − 1 i − 1
As degree(r (x)) > degree(r (x)) > . . . > degree(r (x)) = 0, a consequence
1 2 n
of the preceding lemma is that
degree(u (x)) ≤ degree(g(x)) + m − 1, ∀i ≤ n (6.10)
i
−1
In particular, if g(x) = 1 (computation of the inverse h (x) of h(x)),
the degree of u (x) is always smaller than m.
i
In order to avoid the necessity of computing the quotient and the
remainder of the division of a(x) by b(x), a simpler operation can be
used ([HMV04]). Assume that a(x) is a polynomial of degree s, b(x) a
polynomial of degree t and that s ≥ t. Then define
−1 s – t
q(x) = a (b ) x r(x) = a(x) − b(x)q(x) (6.11)
s t
Actually, these operations correspond to the first step of the
classical division algorithm for polynomials. The coefficient of degree
−1
s of r(x) is equal to a – b a (b ) = 0, so that r(x) is a polynomial of
s s s t
degree less than s and
degree(r(x)) < s = max{degree(a(x)), degree(b(x))} (6.12)

Taking into account that initially a(x) = f(x) and b(x) = h(x), so that
s > t, the main step of the Euclidean algorithm can be substituted by
the following one:
q(x) = a (b ) x r(x) = a(x) − b(x)q(x) (6.13)
−1 s – t
s t
a(x) = b(x) b(x) = r(x)

if degree(a(x)) < degree(b(x)), permute a(x) and b(x)
After a number n of steps, smaller than two times the degree of f,
the degree of r(n) will be equal to 0. In the following algorithm, the
functions pseudo_quotient and pseudo_remainder compute q(x) and r(x)
according to Eq. (6.13).

Algorithm 6.2—Euclidean algorithm, version 2

A := F; B := H; C := Zero; D := G;
while Degree(B) > 0 loop
Q := Pseudo_Quotient(A, B); R := Pseudo_Remainder(A, B);
Next_D := Subtract(C, Product_Mod_F(D, Q, F));
A := B; B := R; C := D; D := Next_D;
if Degree(A) < Degree(B) then Swap(A,B); Swap(C,D);
end if;
end loop;
Z := Product(D, Invert(B(0)));