Page 35 - Hardware Implementation of Finite-Field Arithmetic

18 Cha pte r O n e

s
s
s
5. Given g (x) and h(x) in F , then ( ( )gx + h ( )) = ( ( )) + ( ( )) ,
p
p
p
x
gx
x
h
q
for all s ≥ 0.
n
2
6. If r = (p − 1)/(p − 1), that is r = 1 + p + p + . . . + p n − 1 , and g (x)
is an element of F , then ( g (x)) is an element of F .
r
q p
Example 1.11
4
p = 2, n = 4, f (x) = 1 + x + x so that x ≡ 1 + x mod f (x);
4
α= x is a generator of the cyclic group F *:
16
α = x
1
2
α = x 2
α = x 3
3
4
4
α = x ≡ 1 + x
5
α = x(1 + x) = x + x 2
2
6
2
α = x(x + x ) = x + x 3
2
3
3
4
7
α = x(x + x ) = x + x ≡ 1 + x + x 3
2
α = (α ) = (1 + x) = 1 + x 2
8
4 2
2
9
α = x(1 + x ) = x + x 3
4
α = x(x + x ) = x + x ≡ 1 + x + x 2
3
2
10
α = x(1 + x + x ) = x + x + x 3
2
2
11
2
2
3
4
12
2
3
α = x(x + x + x ) = x + x + x ≡ 1 + x + x + x 3
4
2
3
3
2
α = x(1 + x + x + x ) = x + x + x + x ≡ 1 + x + x 3
2
13
3
2
14
4
α = x(1 + x + x ) = x + x + x ≡ 1 + x 3
3
α = x(1 + x ) = x + x ≡ 1
4
15
3
Given a polynomial g (x) = g + g x + g x + g x , then
2
3
0 1 2 3
2
( g (x)) = g + g x + g x + g x ≡ g + g x + g (1 + x) + g x (1 + x)
2
4
2
2
6
0 1 2 3 0 1 2 3
2
3
= ( g + g ) + g x + ( g + g )x + g x
0 2 2 1 3 3
if ( g (x)) = g (x), then
2
g + g = g , g = g , g + g = g
0 2 0 2 1 1 3 2
thus
g = g = g = 0
1 2 3
and g (x) = g , that is, an element of F (Property 1.8(3)).
0 p
1.3.2 Field Extensions
Definition 1.22 Let E be a subfield of the field F and M any subset of
F. Then the field E(M) is defined as the intersection of all subfields of
F containing both E and M and is called the extension field o f E obtained
θ
by adjoining the elements in M. For a finite subset M = {, ... ,θ },
1 n