Page 32 - Hardware Implementation of Finite-Field Arithmetic

Mathematical Backgr ound 15

while t > 0 loop
if m < t then swap(u, v); swap(b, d); swap(c, e);
swap(m, t); end if;
-1
q := u(m)*(v(t)) *x m-t ; r := u - v*q; bb := b - d*q;
cc := c - e*q;
u := v; v := r; b := d; c := e; d := bb; e := cc;
m := t; t := degree(v);
end loop;
-1
if v(0) = 0 then z := u; else z := 1; b := d*(v(0)) ;
-1
c := e*(v(0)) ; end if;
end if;
1.2.5 Congruences of Polynomials
Definition 1.20 Given three polynomials g (x), h(x), and f (x) in F[x],
g (x) is congruent to h(x) modulo f (x) if f (x) divides g (x) − h(x).
Notation:

g (x) ≡ h(x) (mod f (x))

Properties 1.6 (properties of congruences)
1. g (x) ≡ h(x) (mod f (x)) if and only if ( g (x) mod f (x)) = (h(x),
mod f (x)) (Definition 1.15).
2. The relation g (x) ≡ h(x) (mod f (x)) is an equivalence relation
(reflexive, symmetric, and transitive).
3. If g (x) ≡ h (x) (mod f (x)) and g (x) ≡ h (x) (mod f (x)), then
1 1 2 2

g (x) + h (x) ≡ g (x) + h (x) (mod f (x)), g (x) − h (x) ≡ g (x) − h (x) (mod f (x)),
1 1 2 2 1 1 2 2
g (x)h (x) ≡ g (x)h (x) (mod f (x)) (1.5)
1 1 2 2
From Properties 1.6(1 and 2) it can be seen that the congruence
relation partitions F[x] into equivalence classes. If n is the degree of
f (x) then each equivalence class contains exactly one polynomial of
degree d < n. So, if F is a finite field, then the number of equivalence
classes is equal to |F| , where |F| is the number of elements in F.
n
Furthermore, according to Property 1.6(3), the addition, subtraction,
and multiplication of congruence classes can be defined. As a matter
of fact the set of equivalence classes is isomorphic to

{ g (x) ∈ F[x] | deg ( g) < n}
where the addition, the subtraction, and the multiplication are defi-
ned by

( g (x) + h(x)) mod f (x) ( g (x) − h(x)) mod f (x)
( g (x)h(x)) mod f (x)

The set of equivalence classes is denoted by F[x]/f (x).