Page 166 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF ( p ) 149

−1
For computing z(x) = g(x)h (x) mod f(x), two additional sets of poly-
nomials c(1, x), c(2, x), c(3, x), . . . and d(1, x), d(2, x), d(3, x), . . . are com-
puted in parallel. The initial values are c(0, x) = 0 and d(0, x) = g(x). Then
−1
if b (i, x) = 0: c(i + 1, x) = c(i, x), d(i + 1, x) = d(i, x)x mod f(x)
0
if b (i, x) ≠ 0 and degree(b(i, x)) ≥ degree(a(i, x)):
0
c(i + 1, x) = c(i, x), d(i + 1, x) = cd(i, x)x
−1
−1
where cd(i, x) = c(i, x) − a (i, x)(b (i, x)) d(i, x)
0 0
if b (i, x) ≠ 0 and degree(b(i, x)) < degree(a(i, x)):
0
−1
c(i + 1, x) = d(i, x), d(i + 1, x) = cd(i, x)x
−1
where cd(i, x) = c(i, x) − a (i, x)(b (i, x)) d(i, x)
0 0
The following lemma is demonstrated by induction:
Lemma 6.4
c(i, x)h(x) ≡ a(i, x)g(x) mod f(x)
d(i, x)h(x) ≡ b(i, x)g(x) mod f(x)
Proof
For i = 0: c(0, x)h(x) = 0 and a(0, x)g(x) = f(x)g(x) ≡ 0 mod f(x),
d(0, x)h(x) = g(x)h(x) and b(0, x)g(x) = h(x)g(x).
For i >1 the values of c(i + 1, x) and d(i + 1, x) in function of c(i, x)
and d(i, x) are calculated in the same way as the values of
a(i + 1, x) and b(i + 1, x) in function of a(i, x) and b(i, x), but for the
substitution of the conventional arithmetic operations by mod
f(x) operations.

Thus, according to Eq. (6.20) and Lemma 6.4, d(n, x)h(x) ≡ b(n, x)
g(x) mod f(x) where b(n, x) is a nonzero element of Z , so that (b(n, x)) −1
p
d(n, x)h(x) ≡ g(x) mod f(x) and
−1
g(x)h (x) = (b(n, x)) d(n, x) mod f(x) (6.21)
−1
Given a polynomial w(x) of degree smaller than m over Z , the
p
−1
value of w(x)x mod f(x) is computed as follows: w(x)x mod f(x) =
−1
(w(x) − w f f(x))/x. Assume that a function
−1
0 0
function divide_by_x(a, f: in polynomial) return
polynomial
−1
returning w(x)x mod f(x) has been defined.
Algorithm 6.4—Binary algorithm
A := f; B := h; C := zero; d := g;
while Degree(b) > 0 loop