Page 165 - Hardware Implementation of Finite-Field Arithmetic

148 Cha pte r S i x

if b (i, x) = 0: a(i + 1, x) = a(i, x), b(i + 1, x) = b(i, x)/x
0
if b (i, x) ≠ 0 and degree(b(i, x)) ≥ degree(a(i, x)):
0
a(i + 1, x) = a(i, x), b(i + 1, x) = ab(i, x)/x
where ab(i, x) = a(i, x) − a (i, x)(b (i, x)) b(i, x)
−1
0 0
if b (i, x) ≠ 0 and degree(b(i, x)) < degree(a(i, x)):
0
a(i + 1, x) = b(i, x), b(i + 1, x) = ab(i, x)/x
−1
where ab(i, x) = a(i, x) − a (i, x)(b (i, x)) b(i, x)
0 0
Obviously a(i + 1, x) is not divisible by x and gcd(a(i + 1, x), b(i + 1, x)) =
gcd(a(i, x), b(i, x)) so that
gcd(a(i + 1, x), b(i + 1, x)) = gcd(a(i, x), b(i, x))
= . . . = gcd(a(0, x),b(0, x)) = gcd(a(x), b(x)) (6.18)

In order to demonstrate the convergence of this iteration, compare
degree(a(i + 1, x)) + degree (b(i + 1, x)) with degree(a(i, x)) + degree(b(i, x)):

in the first case degree(a(i + 1, x)) = degree(a(i, x)) and degree(b(i + 1, x)) =
degree(b(i, x)) − 1 if b(i, x) ≠ 0, and degree(b(i + 1, x)) = degree(b(i, x)) if
b(i, x) = 0
in the second case degree(a(i + 1, x)) = degree(a(i, x)) and degree(b(i +
1, x)) = degree(ab(i, x)) − 1 ≤ degree(b(i, x)) −1 if ab(i, x) ≠ 0, and
degree(b(i + 1, x)) < degree(b(i, x)) if ab(i, x) = 0
in the third case degree(a(i + 1, x)) = degree(b(i, x)) and degree(b(i +
1, x)) = degree(ab(i, x)) − 1 ≤ degree(a(i, x)) −1 if ab(i, x) ≠ 0, and
degree(b(i + 1, x)) < degree(a(i, x)) if ab(i, x) = 0
Thus, unless b(i, x) = 0, degree(a(i + 1, x)) + degree(b(i + 1, x)) <
degree(a(i, x)) + degree(b(i, x)). Furthermore, as long as degree(a(i, x)) > 0
and degree(b(i, x)) > 0, then degree(a(i + 1, x)) > 0.

Lemma 6.3 If degree(a(i, x)) > 0 and degree(b(i, x)) > 0, then degree
(a(i + 1, x)) + degree(b(i + 1, x)) < degree(a(i, x)) + degree(b(i, x)), and
degree (a(i + 1, x)) > 0.
In conclusion, after a finite number of steps, say n, b(n, x) will be
a constant polynomial, that is, an element of Z . Thus
p
gcd(a(x), b(x)) = gcd(a(n, x), b(n, x)) with b(n, x) ∈ Z (6.19)
p
In the case where a(x) = f(x) and b(x) = h(x) with degree(h(x)) < m, the
gcd is equal to 1. If b(n, x) = 0, then gcd(a(n, x), b(n, x)) = gcd(a(n, x), 0) = 1,
so that degree(a(n, x)) = 0. Assuming that n is the first index such that
degree(b(n, x)) ≤ 0, then degree(a(n, x)) > 0 (Lemma 6.3), and b(n, x) is a
nonzero element of Z :
p
b(n, x) ∈ Z b(n, x) ≠ 0 (6.20)
p