Page 157 - Hardware Implementation of Finite-Field Arithmetic

140 Cha pte r S i x

Another method is based on the fact that (h(x)) q − 1 mod f(x) = 1 for
any nonzero polynomial h(x), q = p being the number of field
m
elements. Thus, (h(x)) q − 2 h(x) mod f(x) = 1 and
−1
h (x) = (h(x)) q − 2 mod f(x) (6.4)
In this way inversion is substituted by exponentiation.

6.1 Euclidean Algorithm
The classical Euclidean algorithm ([MOV96], [HMV04]) for computing
the gcd of two polynomials a(x) and b(x) consists of a set of integer
divisions:
r (x) = a(x), r (x) = b(x)
0 1
r (x) = r (x)q (x) + r (x)
0 1 1 2
r (x) = r (x)q (x) + r (x) (6.5)
1 2 2 3
. . .
r (x) = r (x)q (x) + r (x)
n − 2 n − 1 n − 1 n
As degree(r (x)) > degree(r (x)) > degree(r (x)) > . . . , after a finite
1 2 3
number of steps, say n, r (x) will be a constant polynomial, that is,
n
an element of Z . Furthermore, gcd(r (x), r (x)) = gcd(r (x),
p n − 1 n n − 2
r (x)) = . . . = gcd(r (x), r (x)) = gcd(a(x), b(x)). Thus,
n − 1 0 1
gcd(a(x), b(x)) = gcd(r (x), r (x)) with r (x) ∈ Z (6.6)
n − 1 n n p
In the particular case where a(x) = f(x) and b(x) = h(x) with
degree(h(x)) < m, the gcd is equal to 1. If r (x) = 0 then gcd(r (x), r (x)) =
n n − 1 n
gcd(r (x), 0) = 1, so that degree(r (x)) = 0. Assuming that n is the first
n − 1 n − 1
index such that degree(r (x)) ≤ 0, the conclusion is that r (x) is a nonzero
n n
element of Z :
p
r (x) ∈ Z r (x) ≠ 0 (6.7)
n p n
For computing z(x) = g(x)h (x) mod f(x), another set of polynomials
−1
u (x), u (x), u (x), . . . are computed in parallel with the computation of
0 1 2
q (x), q (x), q (x), . . . :
1 2 3
u (x) = 0, u (x) = g(x)
0 1
u (x) = u (x) − u (x)q (x)
2 0 1 1
u (x) = u (x) − u (x)q (x) (6.8)
3 1 2 2
. . .
u (x) = u (x) − u (x)q (x)
n n − 2 n − 1 n − 1