Page 158 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF ( p ) 141

The following lemma is demonstrated by induction.
Lemma 6.1
u (x)h(x) ≡ r (x)g(x) mod f(x)
i i

Proof
For i = 0 and 1: u (x)h(x) = 0 and r (x)g(x) = f(x)g(x) ≡ 0 mod f(x),
0 0
u (x)h(x) = g(x)h(x) and r (x)g(x) = h(x)g(x)
1 1
For i ≥ 2: u(x)h(x) = (u (x) − u (x)q (x))h(x) = u (x)h(x) − u (x)
i i − 2 i − 1 i − 1 i − 2 i − 1
q (x)h(x) ≡ r (x)g(x) − r (x)q (x)g(x) = (r (x) − r (x)q (x))g(x) =
i − 1 i − 2 i − 1 i − 1 i − 2 i - 1 i − 1
r (x)g(x)
i
Thus, according to Eq. (6.7) and Lemma 6.1, u (x)h(x) ≡ r (x)g(x)
n n
mod f(x), where r (x) is a nonzero element of Z , so that (r (x)) −1
n p n
u (x)h (x) ≡ g(x) mod f(x) and
n
g(x)h (x) = (r (x)) u (x) mod f(x) (6.9)
−1
−1
n n
Algorithm 6.1—Euclidean algorithm
A := F; B := H; C := zero; D := G;
while Degree(B) > 0 loop
Q := Quotient(A, B); R := Remainder(A, B);
Next_D := Subtract(C, Product_mod_f(D, Q, f));
A := B; B := R; C := D; D := Next_D;
end loop;
Z := Product(D, Invert(B(0)));
An executable Ada file Euclidean_algorithm_polynomials.adb, includ-
ing Algorithm 6.1, is available at www.arithmetic-circuits.org.
As regard the degree of the polynomials u (x) first proof the
i
following lemma.
Lemma 6.2
degree(u (x)) = degree(g(x)) + m − degree(r (x)), ∀i > 0
i i − 1
Proof
For i = 1: u (x) = g(x), r (x) = f(x), degree(r (x)) = m, degree(g(x)) + m −
1 0 0
degree(r (x)) = degree(g(x)).
0
For i = 2: u (x) = u (x) − u (x)q (x) = −g(x)q (x), so that degree(u (x)) =
2 0 1 1 1 2
degree(g(x)) + degree(q (x)). Furthermore r (x) = r (x)q (x) + r (x) so
1 0 1 1 2
that degree(q (x)) = degree(r (x)) − degree(r (x)) = m − degree(r (x)).
1 0 1 1
Finally degree(u (x)) = degree(g(x)) + m − degree(r (x)).
2 1
For i≥ 3: u(x) = u (x) − u (x)q (x). First observe that degree(r (x)) >
i i − 2 i − 1 i − 1 i − 3
degree(r (x)); so, by induction, degree(u (x)) < degree(u (x))
i − 2 i − 2 i − 1
and degree(u (x)) = degree(u (x)) + degree(q (x)) = degree(g(x)) +
i i − 1 i − 1
m− degree(r (x)) + degree(q (x)). Furthermore r (x) = r (x)q (x) +
i − 2 i − 1 i − 2 i − 1 i − 1
r (x), so that degree(q (x)) = degree(r (x)) − degree(r (x)).
i i − 1 i − 2 i − 1