Page 134 - Hardware Implementation of Finite-Field Arithmetic

CHAPTER 5

Operations over

Z [x]/f (x)

p

hapter 5 deals with the study of the arithmetic operations
over the commutative ring Z [x]/f(x), with p prime and f(x)
p
Cnot necessarily irreducible. If f(x) is an irreducible polynomial
m
of degree m over Z , then Z [x]/f(x) is a field with p elements and is
p p
m

called GF(p ) . The elements of Z [x]/f(x) are polynomials of degree at
p
most m – 1 with coefficients from Z .
p
5.1 Addition and Subtraction mod f(x)
Let f(x) be a polynomial of degree m > 0 over Z . Addition and subtraction
p
of two elements a(x), b(x) ∈ Z [x]/f(x) is accomplished in a straightfor-
p
ward way by addition/subtraction of the corresponding coefficients
[MOV96]. Let ax () =∑ m−1 a x , bx () =∑ m−1 b x , and cx () =∑ m−1 c x be
i
i
i
i=0 i i=0 i i=0 i
polynomials in Z [x]/f(x), where the coefficients a , b , c ∈ Z . Then the
i
i
i
p
p
addition/subtraction cx() = a x()± b x() is as follows
m−1
cx () = a x () ± b x () = ∑ c x i with c = a ± b mod p (5.1)
i
i
i
i
i=0
A reduction modulo p (i.e., an addition or subtraction of p) is
necessary whenever the sum or difference of two coefficients a and
i
b is outside the range of [0, . . . , p – 1]. There are no carries propagating
i
between the coefficients. Operations modulo p have been studied in
Chap. 3.
The addition of two elements a(x) + b(x) in Z [x]/f(x) is accom-
p
plished using Eq. (5.1) as follows:
Algorithm 5.1—Addition of polynomials mod p
for i in 0 .. m-1 loop
c(i) := (a(i)+b(i)) mod p;
end loop;
117