Introduction to Finite Fields

Yunghsiang S. Han

Graduate Institute of Communication Engineering, National Taipei University Taiwan E-mail: yshan@mail.ntpu.edu.tw

Y. S. Han

Finite elds

Groups
Let G be a set of elements. A binary operation on G is a rule that assigns to each pair of elements a and b a uniquely dened third element c = a b in G. A binary operation on G is said to be associative if, for any a, b, and c in G, a (b c) = (a b) c. A set G on which a binary operation is dened is called a group if the following conditions are satised: 1. The binary operation is associative. 2. G contains an element e, an identity element of G, such that, for any a G, a e = e a = a. 3. For any element a G, there exists another element a G
Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

such that a a = a a = e. a and a are inverse to each other. A group G is called to be commutative if its binary operation also satises the following condition: for any a and b in G, a b = b a.

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

Properties of Groups
The identity element in a group G is unique. Proof: Suppose there are two identity elements e and e in G. Then e = e e = e. The inverse of a group element is unique.

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

Example of Groups
(Z, +). e = 0 and the inverse of i is i. (Q {0}, ). e = 1 and the inverse of a/b is b/a. ({0, 1}, ), where is exclusive-OR operation. The order of a group is the number of elements in the group. Additive group: ({0, 1, 2, . . . , m 1}, ), where m Z + , and i j i + j mod m. (i j) k=i (j k ). e = 0. 0 < i < m, m 1 is the inverse of i. i j=j i. Multiplicative group: ({1, 2, 3, . . . , p 1}, ), where p is a prime and i j i j mod p.
Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

Proof: Since p is a prime, gcd(i, p) = 1 for all 0 < i < p. By Euclids theorem, a, b Z such that a i + b p = 1. Then a i = b p + 1. If 0 < a < p, then a i = i a = 1. Assume that a p. Then a = q p + r, where r < p. Since gcd(a, p) = 1, r = 0. Hence, r i = (b + q i)p + 1, i.e., r i = i r = 1.

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

Subgroups
H is said to be a subgroup of G if (i) H G and H = . (ii) H is closed under the group operation of G and satises all the conditions of a group. Let G = (Q, +) and H = (Z, +). Then H is a subgroup of G.

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

Fields
Let F be a set of elements on which two binary operations, called addition + and multiplication , are dened. The set F together with the two binary operations + and is a eld if the following conditions are satised: 1. (F, +) is a commutative group. The identity element with respect to addition is called the zero element or the additive identity of F and is denoted by 0. 2. (F {0}, ) is a commutative group. The identity element with respect to multiplication is called the unit element or the multiplicative identity of F and is denoted by 1. 3. Multiplication is distributive over addition; that is, for any three elements a, b and c in F , a (b + c) = a b + a c.
Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

The order of a eld is the number of elements of the eld. A eld with nite order is a nite eld. a b a + (b), where b is the additive inverse of b. a b a b1 , where b1 is the multiplicative inverse of b.

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

Properties of Fields
a F, a 0 = 0 a = 0. Proof: a = a 1 = a (1 + 0) = a + a 0. 0 = a + a = a + (a + a 0). Hence, 0 = 0 + a 0 = a 0. Let a, b F and a, b = 0. Then a b = 0. a b = 0 and a = 0 imply that b = 0. a, b F , (a b) = (a) b = a (b). Proof: 0 = 0 b = (a + (a)) b = a b + (a) b. Similarly, we can prove that (a b) = a (b). Cancellation law: a = 0 and a b = a c imply that b = c. Proof: Since a = 0, a1 (a b) = a1 (a c). Hence, (a1 a) b = (a1 a) c, i.e., b = c.
Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

10

Examples of Fields
(R, +, ). ({0, 1}, , ), binary eld (GF (2)). ({0, 1, 2, 3 . . . , p 1}, , ), prime eld (GF (p)), where p is a prime. There is a prime eld for any prime. It is possible to extend the prime eld GF (p) to a eld of pm elements, GF (pm ), which is called an extension eld of GF (p). Finite elds are also called Galois elds.

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

11

Properties of Finite Fields

Let 1 be the unit element in GF (q ). Since there are only nite number of elements in GF (q ), there must exist two positive integers m and n such that m < n and
m i=1 n m i=1

1=

n i=1

1.

Hence,

1 = 0.
i=1

There must exist a smallest positive integer such that

1 = 0.

This integer is called the characteristic of the eld GF (q ). is a prime.

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

12

Proof: Assume that = km, where 1 < k, m < . Then ( k ) ( m ) km 1 1 = 1 = 0.

i=1 k i=1 m i=1 i=1 i=1

Then
k i=1

1 = 0 or

1 = 0. Contradiction.

1 =
1 i=1

m i=1

1 for any k, m < and k = m.

1 i=1 i=1

1=

1,

2 i=1

1, . . . ,

1,

1 = 0 are distinct elements in

GF (q ). It cab be proved that these elements is a eld, GF (), under the addition and multiplication of GF (q ). GF () is called a subeld of GF (q ).
Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

13

If q = , then q is a power of . Proof: We have GF () a subeld of GF (q ). Let 1 GF (q ) GF (). There are elements in GF (q ) of the form a1 1 , a1 GF (). Since = q , we choose 2 GF (q ) not of the form a1 1 . There are 2 elements in GF (q ) of the form a1 1 + a2 2 . If q = 2 , we are done. Otherwise, we continue in this fashion and will exhaust all elements in GF (q ). Let a be a nonzero element in GF (q ). Then the following powers of a, a1 = a, a2 = a a, a3 = a a a, . . . must be nonzero elements in GF (q ). Since GF (q ) has only nite number of elements, there must exist two positive integers k and m such that k < m and ak = am . Hence, amk = 1. There must exist a smallest positive integer n such that an = 1. n is called the order of the nite eld element a.
Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

14

The powers a1 , a2 , a3 , . . . , an1 , an = 1 are all distinct. The set of these powers form a group under multiplication of GF (q ). A group is said to be cyclic if there exists an element in the group whose powers constitute the whole group. Let a be a nonzero element in GF (q ). Then aq1 = 1. Proof: Let b1 , b2 , . . . , bq1 be the q 1 nonzero elements in GF (q ). Since a b1 , a b2 , . . . , a bq1 are all distinct nonzero elements, we have (a b1 ) (a b2 ) (a bq1 ) = b1 b2 bq1 . Then, aq1 (b1 b2 bq1 ) = b1 b2 bq1 , and then aq1 = 1.
Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

15

If n is the order of a nonzero element a, then n|q 1. Proof: Assume that q 1 = kn + r, where 0 < r < n. Then 1 = aq1 = akn+r = (an )k ar = ar . Contradiction.

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

16

Primitive Element
In GF (q ), a nonzero element a is said to be primitive if the order of a is q 1. The powers of a primitive element generate all the nonzero elements of GF (q ). Every nite eld has a primitive element.
rm 1 r2 Proof: Assume that q > 2. Let h = pr 1 p2 pm be the prime factor decomposition of h = q 1. For every i, the polynomial xh/pi 1 has at most h/pi roots in GF (q ). Hence, there is at least one nonzero element in GF (q ) that are not a root of this polynomial. Let ai be such an element and set

bi = We have
pi i bi
r

h/(pi i ) ai .

i = 1 and the order of bi is a divisor of pr i .

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

17

On the other hand,

pi i bi
r 1

= ai

h/pi

= 1.

i And so the order of bi is pr i . We claim that the element b = b1 b2 bm has order h. Suppose that the order of b is a proper divisor of h and is therefore a divisor of at least one of the m integers h/pi , 1 i m, say of h/p1 . Then we have

1 = bh/p1 = b1

h/p1 h/p2 b2

1 bh/p m .

1 i Now, for 1 < i, pr = 1. Therefore, i divides h/p1 , and hence bi h/p b1 1 = 1. This implies that the order of b1 must divide h/p1 . Contradiction.

h/p

Consider GF (7). We have 31 = 3, 32 = 2, 33 = 6, 34 = 4, 35 = 5, 36 = 1.

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

18

Hence, 3 is a primitive element. Since 41 = 4, 42 = 2, 43 = 1 the order of 4 is 3 and 3|7 1. GF (q ) {0} is a nite cyclic group under multiplication. The number of primitive elements in GF (q ) is (q 1), where is the Eulers function.

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

19

Binary Field Arithmetic

Let f (x) = f (x) f (x) f (x)
n i=0

fi xi and g (x) =

m i=0

gi xi , where fi , gi GF (2).

g (x) f (x) + g (x) with coecients modulo by 2. g (x) f (x) g (x) with coecients modulo by 2. 0 = 0.

f (x) is said to be irreducible if it is not divisible by any polynomial over GF (2) of degree less than n but greater than zero. x2 , x2 + 1, x2 + x are reducible over GF (2). x + 1, x2 + x + 1, x3 + x + 1 are irreducible over GF (2). For any m > 1,, there exists an irreducible polynomial of degree m.
Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

20

Any irreducible polynomial over GF (2) of degree m divides m x2 1 + 1. It will be easy to prove when we learn the construction of an extension eld. x3 + x + 1|x7 + 1, i.e., x7 + 1 = (x4 + x2 + x + 1)(x3 + x + 1). An irreducible polynomial p(x) of degree m is said to be primitive if the smallest positive integer n for which p(x) divides m xn + 1 is n = 2m 1, i.e., p(x)|x2 1 + 1. Since x4 + x + 1|x15 + 1, x4 + x + 1 is primitive. x4 + x3 + x2 + x + 1 is not since x4 + x3 + x2 + x + 1|x5 + 1. For a given m, there may be more than one primitive polynomial of degree m. For all 0, [f (x)]
2

= f (x ).

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

21

Proof: f 2 (x) = (f0 + f1 x + + fn xn )2

= [f0 + (f1 x + f2 x2 + + fn xn )]2

2 = f0 + (f1 x + f2 x2 + + fn xn )2

Expanding the equation above repeatedly, we eventually obtain

2 f 2 (x) = f0 + (f1 x)2 + (f2 x2 )2 + + (fn xn )2 .

Since fi = 0 or 1, fi2 = fi . Hence, we have f 2 (x) = f0 + f1 x2 + f2 (x2 )2 + + fn (x2 )n = f (x2 ).

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

22

List of Primitive Polynomials

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

23

Construction of GF (2m )
Initially, we have two elements 0 and 1 from GF (2) and a new symbol . Dene a multiplication as follows: 1. 0 0 = 0, 01=10=0 11=1 1=1=

0 = 0 = 0, 3. F = {0, 1, , 2 , . . . , j , . . .}.

2. 2 = 3 = j = (j times) Let p(x) be a primitive polynomial of degree m over GF (2). 2 m 1 Assume that p() = 0. Since p(x)|x + 1, m x2 1 + 1 = q (x)p(x). Hence, m m 2 1 + 1 = q ()p() = q () 0 = 0, 2 1 = 1, and i is not 1 for i < 2m 1.
Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

24

Let

F = {0, 1, , , . . . ,
2

2m 2

}.

It can be proved that F {0} is a communicative group under . 1, , , . . . ,

2 2m 2

represent 2m 1 distinct elements.

Next we dene an additive operation + on F such that F forms a communicative group under +. For 0 i < 2m 1, we have xi = qi (x)p(x) + ai (x), where ai (x) = ai0 + ai1 x + ai2 x2 + + ai(m1) xm1 and aij {0, 1}. Since xi and p(x) are relatively prime, we have ai (x) = 0.
Graduate Institute of Communication Engineering, National Taipei University

(1)

Y. S. Han

Finite elds

25

For 0 i = j < 2m 1, ai (x) = aj (x). Proof: Suppose that ai (x) = aj (x). Then xi + xj = = [qi (x) + qj (x)]p(x) + ai (x) + aj (x) [qi (x) + qj (x)]p(x).

This implies that p(x) divides xi (1 + xj i ) (assuming that j > i). Since xi and p(x) are relatively prime, p(x) must divide xj i + 1. This is impossible since j i < 2m 1 and p(x) is a primitive polynomial of degree m which does not divide xn + 1 for n < 2m 1. Contradiction. We have 2m 1 distinct nonzero polynomials ai (x) of degree m 1 or less. Replacing x by in (1) we have i = ai () = ai0 + ai1 + ai2 2 + + ai(m1) m1 .
Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

26

The 2 1 nonzero elements, , , , . . . , in F can be represented by 2m 1 distinct nonzero polynomials of over GF (2) with degree m 1 or less.
m 0 1 2

2 m 2

The 0 in F can be represented by the zero polynomial. Dene an addition + as follows: 1. 0 + 0 = 0. 2. For 0 i, j < 2m 1, 0 + i = i + 0 = , i + j = = (ai0 + ai1 + ai2 2 + + ai(m1) m1 ) + (aj 0 + aj 1 + aj 2 2 + + aj (m1) m1 ) (ai0 + aj 0 ) + (ai1 + aj 1 ) + (ai2 + aj 2 )2 + + (ai(m1) + aj (m1) )m1 ,
Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

27

where ai + aj is carried out in modulo-2 addition. 3. For i = j , (ai0 +aj 0 )+(ai1 +aj 1 )+(ai2 +aj 2 )2 + +(ai(m1) +aj (m1) )m1 is nonzero and must be the polynomial expression for some k in F . It is easy to see that F is a commutative group under + and polynomial multiplication satises distribution law. F is a nite eld of 2m elements.

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

28

Three representations for the elements of GF (24 ) generated by p(x) = 1 + x + x4

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

29

2 3 6

4 12

16 24 48 9 3

Representations of p(z) = + z + 1 Exponential Polynomial Binary Decimal Notation Notation Notation Notation
0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

GF(24).

z4

Minimal Polynomial
x x+1 x4 + x + 1 x4 + x + 1 x4 + x3 + x2 + x + 1 x4 + x + 1 x2 + x + 1 x4 + x3 + x2 + x + 1 x4 + x3 + 1 x4 + x + 1 x4 + x3 + x2 + x + 1 x2 + x + 1 x4 + x3 + 1 x4 + x3 + x2 + x + 1 x4 + x3 + 1 x4 + x3 + 1

0 1 z z2 z3 z+1 z2 + z z3 + z2 z3 + z + 1 z2 + 1 z3 + z z2 + z + 1 z3 + z2 + z + 1 z3 + z2 + z + 1 z3 + z2 + 1 z3 + 1

0000 0001 0010 0100 1000 0011 0110 1100 1011 0101 1010 0111 1110 1111 1101 1001

0 1 2 4 8 3 6 12 11 5 10 7 14 15 13 9





Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

30

Examples of Finite Fields

GF(2) + 0 1 0 1 0 1 1 0 * 0 1 0 1
2+

GF(3) + 0 1 2 +1 0 1 2 0 1 2 1 2 0 2 0 1 * 0 1 2 0 0 0 0 1 2

0 0 1 0 GF(2)[ ]

0 0 1 2 2 1

Primitive polynomial over GF(2)

GF(4) + 0 1 2 3 0 1 2 0 1 2 1 0 3 2 3 0 3 2 1 3 3 2 1 0 * 0 1 2 3 0 0 0 0 0 1 0 3 1 2 2 0 1 2 3 3 0 2 3 1

GF(22), p(x) = 1 + x + x2 ( p( ) = 1 + + 2 = 0 ) 0 1
2

0 1 1+

00 10 01 11

0 2 1 3





Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

31

Examples of Finite Fields

GF(42)

GF(4)[z]/z2+z+2, p(z) = z2+z+2

Exponential Notation Polynomial Notation

Primitive polynomial over GF(4)

Decimal Notation Minimal Polynomial

Binary Notation

0
0 1 2 3 4 5 6 7

=z 15 = 1

8 9 10 11 12 13 14

0 1 z z+2 3z + 2 z + 1 Operate 2 GF(4) 2z 2z + 3 z+3 2z + 2 3 3z 3z + 1 2z + 1 3z + 3

on

00 01 10 12 32 11 02 20 23 13 22 03 30 31 21 33

0 1 4 6 14 5 2 8 11 7 10 3 12 13 9 15

x+1 x2 + x + 2 x2 + x + 3 x2 + 3x + 1 x2 + x + 2 x+2 x2 +2x + 1 x2 + 2x + 2 x2 + x + 3 x2 + 2x + 1 x+3 x2 + 3x + 3 x2 + 3x + 1 x2 + 2x + 2 x2 + 3x + 3





Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

32

Properties of GF (2m )
In GF (2) x4 + x3 + 1 is irreducible; however, GF (24 ), x4 + x3 + 1 = (x + 7 )(x + 11 )(x + 13 )(x + 14 ). Let f (x) be a polynomial with coecients from GF (2). Let be an element in extension eld GF (2m ). If is a root of f (x), then 2 for any 0, is also a root of f (x). The element 2 is called a conjugate of . The 2m 1 nonzero elements of GF (2m ) form all the roots of m x2 1 + 1. Proof: Let be a nonzero element in GF (2m ). It has been 2m 1 2 m 1 shown that = 1. Then + 1 = 0. Hence, every m 2m 1 nonzero element of GF (2 ) is a root of x + 1. Since the m degree of x2 1 + 1 is 2m 1, the 2m 1 nonzero elements of m 2 m 1 GF (2 ) form all the roots of x + 1.
Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

33

The elements of GF (2 ) form all the roots of x

m

2m

+ x.

Let (x) be the polynomial of smallest degree over GF (2) such that ( ) = 0. The (x) is called the minimal polynomial of . (x) is unique. The minimal polynomial (x) of a eld element is irreducible. Proof: Suppose that (x) is not irreducible and that (x) = 1 (x)2 (x), where degrees of 1 (x), 2 (x) are less than that of (x). Since ( ) = 1 ( )2 ( ) = 0, either 1 ( ) = 0 or 2 ( ) = 0. Contradiction. Let f (x) be a polynomial over GF (2). Let (x) be the minimal polynomial of a eld element . If is a root of f (x), then f (x) is divisible by (x). Proof: Let f (x) = a(x)(x) + r(x), where the degree of r(x) is less than that of (x). Since f ( ) = ( ) = 0, we have r( ) = 0.
Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

34

Then r(x) must be 0 since (x) is the minimal polynomial of . The minimal polynomial (x) of an element in GF (2m ) divides 2m x + x. Let f (x) be an irreducible polynomial over GF (2). Let be an element in GF (2m ). Let (x) be the minimal polynomial of . If f ( ) = 0, then (x) = f (x). Let be an element in GF (2m ) and let e be the smallest e non-negative integer such that 2 = . Then f (x) =
e 1 i=0

(x + )

2i

is an irreducible polynomial over GF (2).

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

35

Proof: Consider [e1 ] 2 e 1 i 2 2i [f (x)] = (x + ) = (x + 2 )2 .

i=0 i=0 2i+1

Since (x + ) = x + [f (x)]
2

2i 2

,
i+1

e 1 i=0

(x2 + 2

)=

(x2 + 2 )

[e1 ] 2 2i 2 2e = (x + ) (x + )
i=1

i=1

Since 2 = , then [f (x)] =

2 e 1 i=0

(x2 + 2 ) = f (x2 ).

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

36

Let f (x) = f0 + f1 x + + fe xe , where fe = 1. Expand [f (x)]2 = (f0 + f1 x + + fe xe )2 e e e = fi2 x2i + (1 + 1) fi fj xi+j

i=0 e i=0 i=0
j =0 i=j

fi2 x2i .

Then, for 0 i e, we obtain fi = fi2 . This holds only when fi = 0 or 1. Now suppose that f (x) is no irreducible over GF (2) and f (x) = a(x)b(x). Since f ( ) = 0, either a( ) = 0 or b( ) = 0. If e1 a( ) = 0, a(x) has , 2 , . . . , 2 as roots, so a(x) has degree e
Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

37

and a(x) = f (x). Similar argument can be applied to the case b( ) = 0. Let (x) be the minimal polynomial of an element in GF (2m ). e Let e be the smallest integer such that 2 = . Then (x) =
e 1 i=0

(x + 2 ).

Let (x) be the minimal polynomial of an element in GF (2m ). Let e be the degree of (x). Then e is the smallest integer such e that 2 = . Moreover, e m. The degree of the minimal polynomial of any element in GF (2m ) divides m.

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

38

Minimal polynomials of the elements in GF(24) generated by p(x)=x4+x+1 Conjugate roots 0 1 , 2, 4, 8 3, 6, 9, 12 5, 10 7, 11, 13, 14 minimal polynomials x x+1 x4+ x +1 x4+ x3+ x2+ x +1 x2+ x +1 x4+ x3+ 1

e.g. X15-1= (x+1)(x2+x+1) (x4+x+1) (x4+x3+1) (x4+x3+x2+x+1) over GF(2) X15-1= (x- 0) (x- 5)(x- 10) (x- 1)(x- 2)(x- 4)(x- 8) over GF(24)
15

=1

(x- 7)(x-

14)(x- 13)(x- 11)

(x- 3)(x- 6)(x-

12)(x- 9)

Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

39

If is a primitive element of GF (2m ), all its conjugates 2 2 , 2 , . . ., are also primitive elements of GF (2m ). Proof: Let n be the order of 2 for > 0. Then ( ) =
2 n n2

= 1.

It has been proved that n divides 2m 1, 2m 1 = k n. Since is a primitive element of GF (2m ), its order is 2m 1. Hence, 2m 1|n2 . Since 2 and 2m 1 are relatively prime, n must be divisible by 2m 1, say n = q (2m 1). Then n = 2m 1. Consequently, 2 is also a primitive element of GF (2m ). If is an element of order n in GF (2m ), all its conjugates have the same order n.
Graduate Institute of Communication Engineering, National Taipei University

Y. S. Han

Finite elds

40

2 3 6

4 12

16 24 48 9 3

Representations of p(z) = + z + 1 Exponential Polynomial Binary Decimal Notation Notation Notation Notation
0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

GF(24).

z4

Minimal Polynomial
x x+1 x4 + x + 1 x4 + x + 1 x4 + x3 + x2 + x + 1 x4 + x + 1 x2 + x + 1 x4 + x3 + x2 + x + 1 x4 + x3 + 1 x4 + x + 1 x4 + x3 + x2 + x + 1 x2 + x + 1 x4 + x3 + 1 x4 + x3 + x2 + x + 1 x4 + x3 + 1 x4 + x3 + 1

0 1 z z2 z3 z+1 z2 + z z3 + z2 z3 + z + 1 z2 + 1 z3 + z z2 + z + 1 z3 + z2 + z + 1 z3 + z2 + z + 1 z3 + z2 + 1 z3 + 1

0000 0001 0010 0100 1000 0011 0110 1100 1011 0101 1010 0111 1110 1111 1101 1001

0 1 2 4 8 3 6 12 11 5 10 7 14 15 13 9





Graduate Institute of Communication Engineering, National Taipei University