Page 167 - Hardware Implementation of Finite-Field Arithmetic

150 Cha pte r S i x

if b(0) = 0 then b := Shift_One(b);
d := Divide_By_X(d, F);
else
coef := (A(0)*Invert(B(0))) mod p;
Old_b := b; Old_d := d;
b := Shift_One(Subtract(A, Product(B, coef)));
d := Divide_By_X(Subtract(C, Product(D, coef)),F);
if Degree(a) > Degree(Old_b) then a := Old_b;
c := Old_d;
end if;
end if;
end loop;
Z := Product(d, Invert(b(0)));
An executable Ada file binary_polynomials.adb, including Algo-
rithm 6.4, is available at www.arithmetic-circuits.org.
Instead of computing the degree of a(i, x) and b(i, x) at each step,
a better solution consists of defining upper bounds α and β ([DS06])
i i
such that
degree(a(i, x)) ≤ α degree(b(i, x)) ≤ β
i i
Initially a(0, x) = f(x), α = m, b(0, x) = h(x), β = m − 1. The two
0 0
sequences a(1, x), a(2, x), a(3, x), . . . and b(1, x), b(2, x), b(3, x), . . . of
polynomials and the two sequences α , α , α , . . . and β , β , β , . . . of
1 2 3 1 2 3
integers are generated as follows:
if b (i, x) = 0: a(i + 1, x) = a(i, x), b(i + 1, x) = b(i, x)/x,
0
α = α , β = β − 1
i + 1 i i + 1 i
if b (i, x) ≠ 0 and β ≥ α :
0 i i
a(i + 1, x) = a(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
α = α , β = β − 1
i + 1 i i + 1 i
if b (i, x) ≠ 0 and β < α :
0 i i
a(i + 1, x) = b(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
−1
0 0 i + 1 i i + 1 i
In order to demonstrate the convergence of this iteration, observe that

α + β = α + β − 1 (6.22)
i + 1 i + 1 i i
Also note that as long as α ≥ 0 and β ≥ 0, α ≥ 0. In conclusion,
i i i + 1
after a finite number of steps, say n, β < 0, that is degree(b(n, x)) < 0
n
(= −∞), and thus b(n, x) = 0. As gcd(a(n, x), b(n, x)) = gcd(a(0, x), b(0, x)) =
gcd( f(x), h(x)) = 1 and b(n, x) = 0, then
a(n, x) ∈ Z a(n, x) ≠ 0 (6.23)
p