Page 33 - Hardware Implementation of Finite-Field Arithmetic

16 Cha pte r O n e

Properties 1.7
1. F[x]/f (x) is a commutative ring.
2. If f (x) is irreducible, then F[x]/f (x) is a field.

Proofs
1. Consequence of Property 1.6(3).
2. If f (x) is irreducible, then the greatest common divisor of f (x)
and g (x) ≠ 0 is 1. Using the Euclidean algorithm, b(x) and c(x)
can be computed such that

1 = b(x)f (x) + c(x)g (x)
and

− 1
c(x) = ( g (x)) mod f (x)

Example 1.10 Let f (x) = x + x + 1 ∈ Z [x]. From the irreducibility of
3
2
f (x) over Z , it follows that Z [x]/f (x) is a field. In this case Z = Z ,
2 2 p 2
n
3
and the field Z [x]/f (x) has the p = 2 elements (residue classes) [0],
2
2
2
2
2
[1], [x], [x ], [x + 1], [x + 1], [x + x], [x + x + 1]. The addition and mul-
tiplication tables are obtained by performing the required operations
and by carrying out reduction mod f (x) if necessary (Table 1.2):
+ [0] [1] [x] [x ] [x + 1] [x + 1] [x + x] [x + x + 1]
2
2
2
2
2
2
2
[0] [0] [1] [x] [x ] [x + 1] [x + 1] [x + x] [x + x + 1]
2
2
2
2
2
[1] [1] [0] [x + 1] [x + 1] [x] [x ] [x + x + 1] [x + x]
2
[x] [x] [x + 1] [0] [x + x] [1] [x + x + 1] [x ] [x + 1]
2
2
2
2
[x ] 2 [x ] [x + 1] [x + x] [0] [x + x + 1] [1] [x] [x + 1]
2
2
2
2
2
2
2
[x + 1] [x + 1] [x] [1] [x + x + 1] [0] [x + x] [x + 1] [x ]
2
2
2
2
2
[x + 1] [x + 1] [x ] [x + x + 1] [1] [x + x] [0] [x + 1] [x]
2
2
2
[x + x] [x + x] [x + x + 1] [x ] [x] [x + 1] [x + 1] [0] [1]
2
2
2
2
2
2
2
[x + x + 1] [x + x + 1] [x + x] [x + 1] [x + 1] [x ] [x] [1] [0]
⋅ [0] [1] [x] [x ] [x + 1] [x + 1] [x + x] [x + x + 1]
2
2
2
2
[0] [0] [0] [0] [0] [0] [0] [0] [0]
[1] [0] [1] [x] [x ] [x + 1] [x + 1] [x + x] [x + x + 1]
2
2
2
2
2
2
2
2
[x] [0] [x] [x ] [x + 1] [x + x] [1] [x + x + 1] [x + 1]
2
2
2
2
[x ] 2 [0] [x ] [x + 1] [x + x] [x + x + 1] [x] [x + 1] [1]
2
[x + 1] [0] [x + 1] [x + x] [x + x + 1] [x + 1] [x ] [1] [x]
2
2
2
2
2
2
[x + 1] [0] [x + 1] [1] [x] [x ] [x + x + 1] [x + 1] [x + x]
2
2
2
2
2
2
2
[x + x] [0] [x + x] [x + x + 1] [x + 1] [1] [x + 1] [x] [x ]
2
2
2
2
[x + x + 1] [0] [x + x + 1] [x + 1] [1] [x] [x + x] [x ] [x + 1]
2
TABLE 1.2 Addition and Multiplication over Z [x]/f(x)
2