1.2
Abstract Algebra

Abstract algebra ^［2，3］ studies algebra system，which is composed of sets and operations on the sets.

Definition 1.2.1（Binary Operation） A binary operation on a set S is a mapping from the cartesian product S × S to S .

Definition 1.2.2（Homomorphism） Let（ A ，◦）and（ B ，◦'）be binary algebraic system.If there is a mapping φ between A and B such that

φ （ a ₁ ◦ a ₂ ）= φ （ a ₁ ）◦' φ （ a ₂ ）， a ₁ ， a ₂ ∈ A ， φ （ a ₁ ）， φ （ a ₂ ）∈ B

Then φ is called a homomorphism from A to B ，or A and B are homomorphic.Further，if φ is an injection mapping，then it is called an isomorphism .Isomorphism implies that（ A ，◦）and（ B ，◦'）have identical algebraic structure except that the symbol identification and symbol order may be different.

1.2.1　Group

Definition 1.2.3（Group） If a set G and a binary operation ◦ over G has the following properties

P ₁ ：◦ is closed，i.e.，∀ a ， b ∈ G ， a ◦ b ∈ G .

P ₂ ：◦ is associative，i.e.，∀ a ， b ， c ∈ G ， a ◦（ b ◦ c ）=（ a ◦ b ）◦ c .

P ₃ ：There is a unique identity element e in G such that∀ a ∈ G ， a ◦ e = e ◦ a = a .

P ₄ ：Each element a in G has a unique inverse element a ^-1 such that a ◦ a ^-1 = a ^-1 ◦ a = e .

then G is a group under ◦，or briefly ＜ G ，◦＞ is a group.

The number of elements in a group G is called the order of G .If the order is finite，then G is a finite group，which could be illustrated by a group table.Figure 1.2.1 show a finite group composed of two and three elements respectively.It is not difficult to find that any element in the group table appears in each row and column only once.In the sense of isomorphism，the groups with one element，two elements and three elements are all unique，but the group with more than four elements is not unique.

Specifically，if ◦ represents addition（multiplication），it is called addition（multiplication）group.In an addition（multiplication）group，it traditionally uses +（·）to denote the binary operation，and use - a （ a ^-1 ）to denote the inverse element of a .By using inverse elements，we can leverage the familiar inverse operations of + or ·.For example，subtraction is defined by a - b = a +（- b ）；division is defined by a / b = a ·（ b ^-1 ）.The symbol 0（1）is always used to denote the identity element of an addition（multiplication）group.

Moreover，for any element a in an additive group G and any positive integer n ，using na to represent the sum of a number of n element a ，i.e.， a + a +…+ a .Similarly，if G is a multiplication group，using a ⁿ to represent the product of a number of n element a ，i.e.， aa … a .However，it should be noted that na （ a ⁿ ）is just a concise expression. na （or a ⁿ ）should not be seen as the multiplication of n with a （or the n th power of a ）.Actually， n is not an element of group G ，so n and a cannot operate on G .For brevity，unless otherwise specified in the following text，the multiplicative group and multiplicative identification are taken as examples.Here are some concepts related to groups.

If ＜ G ，◦＞ is closed and associative，but the identity element and inverse element do not exist，then ＜ G ，◦＞ is called semigroup .If ◦ is commutative，i.e.， a ， bG ∀∈， a ◦ b = b ◦ a ，then ＜ G ，◦＞ is called abelian group .For a group ＜ G ，◦＞，if there exists a nonempty subset H with the properties of（P ₁ ～P ₄ ）in the definition of the group under ◦，then H is called the subgroup of G under ◦.

Definition 1.2.4（Cyclic Group） Let G be a multiplication group and let a ∈ G .It can be proved that H =｛ a ⁿ | n ∈Z｝is a subgroup of G . H is the minimal subgroup containing a and is called the cyclic subgroup of G generated by a .The order of H is also called the order of a .If G is generated by an element a ，then G is called cyclic group .

Example 1.2.1

（1）The sets of integers（Z），rational numbers（Q），real numbers（R），and complex numbers（C）under general addition + are abelian groups.The identity element is 0.The inverse element of a is（- a ）.＜Z，+＞ is a subgroup of ＜Q ，+＞，which is furtherly a subgroup of ＜R，+＞.

（2）All nonzero rational numbers｛Q \｛0｝｝under general multiplication · is an abelian group.The identity element is 1.The inverse element of a is（ a ^-1 ）.

（3）All nonzero integers Z ^* =｛Z\｛0｝｝under general multiplication · is not a group，since each element other than 1 does not have an inverse element.

（4）Let G =｛0，1，…， m -1｝with m being a positive integer.Define a binary operation of modulo（ m ）addition + _m as a + _m b =（ a + b ）mod m ，then ＜ G ，+ _m ＞ is an abelian group.For example，let m =6，the addition table is as Figure 1.2.2.The identity is 0.The inverse elements are（-1）=5，（-2）=4，（-3）=3，（-4）=2，（-5）=1.

（5）Let G =｛1，2，…， p -1｝with p being a positive prime number.Define a binary operation of modulo（ p ）multiplication × _p as a × _p b =（ a · b ）mod p ，then ＜ G ，× _p ＞ is an abelian group.For example，the multiplication table for p =5 is as Figure 1.2.3（a）shows.The identity is 1.The inverse elements are（1 ^-1 ）=1，（2 ^-1 ）=3，（3 ^-1 ）=2，（4 ^-1 ）=4.However，if p is not a prime number，it is easy to verify ＜ G ，× _p ＞ is not a group.For example，Figure 1.2.3（b）shows the case as p =4.A new element 0 other than｛1，2，3，4｝is generated so × ₄ is not closed.

Definition 1.2.5（Equivalence Relation） Let H be a subgroup of G .∀ a，b ∈ G ，

If a ^-1 b ∈ H ，then it is called a is left equivalent to b ，denoted by a ～ _L b.

If ab ^-1 ∈ H ，then it is called a is right equivalent to b ，denoted by a ～ _R b.

Definition 1.2.6（Cosets） Let H be a subgroup of G .The subset aH =｛ ah | h ∈ G ｝is the left

coset of H containing a ，while the subset Ha =｛ ha | h ∈ G ｝is the right coset of H containing a .If the left coset is the same to the right coset，then H is called a normal subgroup of G .

Example 1.2.2

（1） H =｛0，2｝is a subgroup of modulo（4）addition group（Z ₄ ，+ ₄ ）.The coset of H containing the element 1 is｛1，3｝.

（2） H =（3Z，+）is a subgroup of G =（Z，+）.The coset of H containing 1 and 2 are｛1+3Z ｝and｛2+3Z ｝，as given below.

3Z=｛…，-9，-6，-3，0，3，6，9， ^… ｝

1+3Z=｛…，-8，-5，-2，1，4，7，10，…｝

2+3Z=｛…，-7，-4，-1，2，5，8，11，…｝

It can be found from this example that H and its cosets take identical order，and they become a partition of G .

Theorem 1.2.1（Theorem of Lagrange） Let H be a subgroup of a finite group G .Then the order of H is a divisor of the order of G .

1.2.2　Ring

A group defines an algebraic operation and its inverse operation on a set.For example，an addition group defines addition and subtraction，and a multiplication group defines multiplication and division.However，many calculations and applications need to define both addition and multiplication on the same set，and the ring is such an algebraic system.

Definition 1.2.7（Ring） If a nonempty set R together with two binary operations + and · over R has the following properties.

P ₁ ：＜ R ，+＞ is an abelian group .

P ₂ ：·is associative.

P ₃ ：∀ a ， b ， c ∈ G ，the left and right distribution law of multiplication over addition hold，i.e.， a ·（ b + c ）= a · b + a · c ；（ b + c ）· a = b · a + c · a .

then ＜ R ，+，·＞ is a ring.

It can be seen from this definition that although the ring defines multiplication operation，it does not require the inverse operation of multiplication（i.e.，division）to be true，so it is not required that all non-zero elements in the ring must have the multiplicative inverse element.In addition，the definition of rings does not require multiplication to satisfy commutative law.Two special rings can be obtained by supplementing these requirements.Specifically，if every non-zero element in the ring R has a multiplicative inverse element，then R is called division ring .Further，if the multiplication of a division ring R satisfies the commutative law，that is，the non-zero elements in R form a commutative group with respect to multiplication，then it is called field .The inclusion relationship among ring，division ring and field is shown in Figure 1.2.4.

Example 1.2.3

（1）（Z，+，·），（Q ，+，·），（R，+，·），（C，+，·）under general addition + and · are rings.The addition identity element is 0.The multiplication identity element is 1.（Q ，+，·），（R，+，·），（C，+，·）are still fields.（Z，+，·）is not a division ring or a field，since other than 1 and -1，all non-zero elements do not have the multiplicative inverse element.

（2）Let M _n （Z）denotes a n × n matrix with elements taken from integrals Z.（ M _n （Z），+，·）is a ring，in which + and · represent the operation of addition and multiplication of matrix.The addition identity element and the multiplication identity element are null matrix and identity matrix respectively.It should be noted that the · operation in this ring is not commutative and the inverse element may not exist for non-zero matrix of M _n （Z），so it is not a division ring or a field.

（3）（ n Z，+，·）is a ring.

（4）Let Z［ x ］ denote polynomials with coefficients drawn from integrals Z.（Z［ x ］，+，·）is a ring，in which + and · represent the operation of addition and multiplication of polynomials.Generally，Let R ［ x ］ denote polynomials with coefficients drawn from a ring R ，then（ R ［ x ］，+，·）is a ring，which is called polynomial ring.It is a very important ring，which will be discussed later.

（5）（Z ₄ ，+ ₄ ，× ₄ ）is a ring.Z ₄ =｛0，1，2，3｝.+ ₄ and × ₄ denote the modulo-4 addition and multiplication respectively.In this ring，the addition identity element is 0；the multiplication identity element is 1.The element 1 and 3 have inverse elements，but 2 does not，so it is not a division ring or a field.

Let us review a problem of solving equation.The equation x ² -5 x +6=0，（ x -2）（ x -3）=0 is obtained through factorization，and the roots of the equation are x =2 and x =3.It is familiar knowledge.The solution is carried out in real numbers by default.However，if it is solved in the ring（Z ₁₂ ，+ ₁₂ ，× ₁₂ ），one will get some new discoveries.Since modulo-12 addition and modulo-12 multiplication are used，the results of 2× ₁₂ 6，3× ₁₂ 4，6× ₁₂ 6，4× ₁₂ 9，8× ₁₂ 9，6× ₁₂ 10 are all 0，for equation（ x -2）（ x -3）=0，in addition to x =2 and x =3， x =6 and x =11 are also the roots of the equation.

Definition 1.2.8（0 divisors） If a and b are two non-zero elements of a ring R such that ab =0，then a and b are 0 divisors.

Example 1.2.4

（1）In the ring（Z ₁₂ ，+ ₁₂ ，× ₁₂ ），2，3，4，6，8，9，and 10 are 0 divisors.Generally，in the ring Z _n ，all non-zero numbers that are not relatively prime to n are 0 divisors.

（2）In the ring（Z _p ，+ _p ，× _p ），with p being a prime number，there is no 0 divisors.

Due to the existence of 0 divisors，some familiar operation rules will change.For example，in real numbers，multiplication satisfies the elimination law，that is， b = c can be deduced from ab = ac ，but it is obviously wrong that 4=8 is deduced from 4× ₁₂ 9=8× ₁₂ 9 in Z ₁₂ .For another example，in real numbers，for the equation ax = b （ a ≠0）can be solved by x = a ^-1 b ，but in Z ₁₂ ，if a is a 0 divisor， a ^-1 does not exist.Thus，the definition of the ring is too loose to solve equations，it should be restricted on multiplication.

Definition 1.2.9（Integral domain） Let R be a ring.If the following properties are satisfied， R is called an integral domain.

P ₁ ：The multiplication is commutative.

P ₂ ：There is multiplication identity.

P ₃ ：There is no 0 divisors.

Example 1.2.5

（1）The ring（Z _p ，+ _p ，× _p ）with p being a prime number is an integral domain.

（2）（Z，+，·）is an integral domain.+ and · are addition and multiplication in general sense.

However，the integral domain still does not require that each non-zero element must have a multiplicative inverse.If this condition is supplemented，it becomes a field.

Definition 1.2.10（Polynomial） A polynomial f （ x ）with coefficients drawn from a ring R is as following.

where a _i ∈ R and a _n ≠0， a _i are coefficients of f （ x ）， n is the degree of f （ x ）， x is called indeterminate.

The two polynomials f （ x ）and g （ x ）whose coefficients are taken from the same ring R can make operations of addition，subtraction，multiplication and division.The result is a new polynomial.The operation rule is that the coefficients of the two polynomials are added，subtracted，multiplied and divided on R .Specifically，let the two polynomials be

The degree n and m can be identical or different.When n ≠ m ，the two degrees can be unified by supplementing higher terms with a coefficient of 0 for the lower degree polynomial.Therefore，for brevity，the following assumes that both degrees are n .The operation rules of addition，subtraction，multiplication and division of f （ x ）and g （ x ）are given below.

1.Addition

2.Subtraction

3.Multiplication

4.Division

The two polynomials use long division，and the coefficients are added，subtracted and multiplied on the ring R during the operation.

Example 1.2.6 f （ x ）= x ⁴ -3 x ³ +2 x ² +4 x -1 and g （ x ）= x ² -2 x +3 are defined on Z ₅ .

f （ x ）+ g （ x ）=（ x ⁴ -3 x ³ +2 x ² +4 x -1）+（ x ² -2 x +3）= x ⁴ -3 x ³ +3 x ² +2 x +2

f （ x ）- g （ x ）=（ x ⁴ -3 x ³ +2 x ² +4 x -1）-（ x ² -2 x +3）= x ⁴ -3 x ³ + x ² + x -4

f （ x ）/ g （ x ）is showed by Figure 1.2.5.

Because we are very familiar with the operations in real numbers，beginners may not be accustomed to the operations on a general ring R （such as Z _m ）.In fact，we only need to grasp the rule that the operations of two polynomials on a ring R are the operations of the coefficients on R .For example，on the ring Z ₂ ，（ x +1） ² = x ² +2 x +1= x ² +1 since 2（mod）2=0.

Let R ［ x ］ denote the set of polynomials whose coefficients are taken from the ring R ，it can be proved that under the addition and multiplication defined above， R ［ x ］ also forms a ring，which is called polynomial ring ，and R is a subring of R ［ x ］.If R is a commutative ring，then R ［ x ］ is also a commutative ring，and the elements in R are the constant polynomials in R ［ x ］.

One can find from the division f （ x ）/ g （ x ）in Figure 1.2.5 that two polynomials are not necessarily divisible.If q （ x ）and r （ x ）are used to represent the quotient and remainder，then f （ x ）can be written as f （ x ）= q （ x ） g （ x ）+ r （ x ）.Therefore，polynomial division is a little similar to the division on integer.Indeed，we will gradually see that polynomial ring and integer ring have many similarities.

Definition 1.2.11 If a non-constant polynomial f （ x ）∈ R ［ x ］ whose coefficients are taken from ring R cannot be decomposed into the product of two polynomials g （ x ）and h （ x ）whose degrees are lower than f （ x ），then f （ x ）is called an irreducible polynomial on R .On the contrary， f （ x ）is called a reducible polynomial on R .

The role of irreducible polynomials in the polynomial ring R ［ x ］ is similar to that of prime numbers in the integer ring Z.There is the unique factorization theorem in the integer ring Z，that is，for each integer n greater than 1，it can be uniquely expressed as the product of a finite number of prime numbers，such as n = p ₁ p ₂ … p _r .Similarly，any polynomial f （ x ）in a polynomial ring R ［ x ］ can be uniquely expressed as the product of a finite number of irreducible polynomials，i.e.， f （ x ）= p ₁ （ x ） p ₂ （ x ）… p _r （ x ）.It is similar to integer.

Example 1.2.7 f （ x ）= x ³ +3 x +2 is an irreducible polynomial on Z ₅ . g （ x ）= x ² +3 x +2 is a reducible polynomial on Z ₅ .It can be factorized into（ x +1）（ x +2）.

1.2.3　Field

Ring defines three algebraic operations of addition，subtraction and multiplication on the set.However，ones often need to carry out four operations of addition，subtraction，multiplication and division.To meet this requirement，the multiplication should be inversible.Such an algebraic system is called field.

Definition 1.2.12（Field） If a non-empty set F together with two binary operations +and · over F has the following properties.

P ₁ ：＜ F ，+＞ is an abelian group，with the addition identity being 0.

P ₂ ：＜ F \｛0｝，·＞ is an abelian group，with the multiplication identity being 1.

P ₃ ：∀ a ， b ， c ∈ G ，the left and right distribution law of multiplication over addition hold，i.e.， a ·（ b + c ）= ab + ac ；（ b + c ）· a = ba + ca

then ＜ F ，+，·＞ is a field.

Use - a （ a ^-1 ）to denote the addition（multiplication）inverse element of a .A field with infinite number of elements is called infinite field.A field with finite number of elements is called finite field or Galois field .The number of elements in a finite field F is called the order of F .

Example 1.2.8 ＜Q ，+，·＞ ，＜R，+，·＞ ，＜C，+，·＞ are fields.However，＜Z，+，·＞ is not a field since ＜Z，·＞ is not a group.

From the definition of field，it can be seen that the field is a perfect algebraic system capable of addition，subtraction，multiplication and division.Especially，finite field has become the mathematical basis of coding.In the following，we will focus on finite field.

Example 1.2.9 Let F ₂ =｛0，1｝，then ＜ F ₂ ，+ ₂ ，× ₂ ＞ is a finite field.The tables of addition and multiplication are given by Figure 1.2.6.

Example 1.2.10 More generally，let F =｛0，1，…， p ｝with p be a positive prime number，then ＜ F ，+ _p ，× _p ＞ is a finite field.This is the first class of finite field.In this book，we concisely denoted this finite field by F _p or GF（ p ）.Figure 1.2.7 gives the addition table and multiplication table of GF（7）.

The example shows if p is a positive prime number，then ＜ F ，+ _p ，× _p ＞ is a finite field.Example 1.2.3 shows if p is not a positive prime number，then ＜ F ，+ _p ，× _p ＞ is not a finite field.Take p =4 as an example.＜ F ，+ ₄ ，× ₄ ＞ is a ring but not a finite field because ＜ F \｛0｝，× ₄ ＞ is not an abelian group.See the × ₄ multiplication table in Figure 1.2.3（b）.Then，a question arises，is there a field with the order of 4？ The answer is yes，as shown in Figure 1.2.8.Note that the operation rules of this field are different from modulo-4 addition and modulo-4 multiplication.

We will see later that for any prime number p and any positive integer m ，there is a finite field GF（ p ^m ）composed of p ^m elements or with the order of p ^m .

1.2.4　Finite Field

For a finite fiel d ＜ F ，+，·＞，define

Since there are finite number of elements within F and + being closed，for each positive integer m ，there must be an integer n （＞ m ）such that

It is to say there must be the least positive integer λ such that . λ is called the characteristic of this field.

Definition 1.2.13 For a finite field ＜ F ，+，·＞，the least positive integer λ with is called the characteristic of this field.

Theorem 1.2.2 Assume λ is the characteristic of a finite field F ，then it has the property

For each non-zero element a in a finite field ＜ F ，+，·＞，define

a ¹ = a

a ² = a · a

a ^m = a · a … a

Since there are a finite number of elements within F and · being closed，the multiplication result defined above must be repeated from a certain moment.Or，for each positive integer k ，there must be an integer m ＞ k such that

a ^k = a ^m ，　 or equivalently a ^{m - k} =1

It implies that there must be a minimum positive integer n for any non-zero element a in GF（ p ）such that a ⁿ =1. n is called the order of a .

Definition 1.2.14 For each non-zero element a in a finite field ＜ F ，+，·＞，the least positive integer n with a ⁿ =1 is called the order of a .

Example 1.2.11 In F ₇ ，we have

1 ¹ =1

2 ¹ =2；2 ² =4；2 ³ =1

3 ¹ =3；3 ² =2；3 ³ =6；3 ⁴ =4；3 ⁵ =5；3 ⁶ =1

4 ¹ =4；4 ² =2；4 ³ =1

5 ¹ =5；5 ² =4；5 ³ =6；5 ⁴ =2；5 ⁵ =3；5 ⁶ =1

6 ¹ =6；6 ² =1

So，the order of the elements 1，2，3，4，5，6 is 1，3，6，3，6，2，respectively.

Theorem 1.2.3 Each non-zero element of F _p satisfies a ^{p -1} =1.

Proof：Let b ₁ ， b ₂ ，…， b _{p -1} be non-zero elements in F _p .Obviously， ab ₁ ， ab ₂ ，…， ab _{p -1} must be a number of p -1 non-zero elements which are different from each other.Because there are in total p -1 non-zero elements in F _p ，it implies（ ab ₁ ）（ ab ₂ ）…（ ab _{p -1} ）= b ₁ b ₂ … b _{p -1} .So we have a ^{p -1} =1.

Since any non-zero element a with the order of n in a finite field F _p must have a ⁿ =1，one can deduct a result from Theorem 1.2.3 that the order of any non-zero element a in F _p must be divisible by p -1.

Definition 1.2.15 In F _p ，an element with the order of p -1 is called a primitive element .

Therefore，a primitive element can generate all non-zero elements through power operation.In Example 1.2.11，elements 3 and 5 are two primitive elements.

1.2.5　Extension Fields

Similar to subgroups and subrings，there are also the concept of subfields.For example，the rational number field Q is a subfield of the real number field R，which is further the subfield of the complex number field C.The procedure of generating extension fields from subfields is called extension.Next，we discuss how to get an extension field GF（ p ^m ）from Z _p .

Theorem 1.2.4 The roots of a polynomial defined on a field may exist in its extension field.

As an example， x ² +1=0 does not have a root in R，but have two roots in C.

Definition 1.2.16（Algebraic Closure） For any field F ，put all the roots of all polynomials in the polynomial ring F ［ x ］ together to form a set Ω .It can be proved that Ω is an extension field of F . Ω is called the algebraic closure of F .Specially，for Z _p ，the algebraic closure is denoted by Ω _p .

Theorem 1.2.5 Any m -degree irreducible polynomial on the field Z _p can divide .

As an example， f （ x ）= x ² + x +2 is an irreducible polynomial with the degree of 2 on Z ₃ .It could be verified by long division that f （ x ）could divide x ⁸ -1.

Definition 1.2.17（Primitive Polynomial） Let a m -degree irreducible polynomial f （ x ）on the field Z _p divide x ⁿ -1.If the least number of n = p ^m -1 in condition that is divisible，then the irreducible polynomial f （ x ）is called a primitive polynomial.

As an example， x ² + x +2 is a primitive polynomial on Z ₃ . x ² +1 is an irreducible polynomial but not a primitive polynomial，since it can divide x ⁴ -1.

Theorem 1.2.6 Let f （ x ）be a m -degree primitive polynomial on Z _p .Assume α to be a root in Ω _p .Then｛0，1， α ， α ² ，…， α ^{pm -2} ｝is a finite field GF（ p ^m ）.

Example 1.2.12 x ² + x +2 is a primitive polynomial on Z ₃ .Assume α is a root of x ² + x +2=0，i.e.， α ² + α +2=0.Then it can be verified｛0，1， α ， α ² ， α ³ ， α ⁴ ， α ⁵ ， α ⁶ ， α ⁷ ｝is a finite field GF（9）.In order to discuss the addition of the field，first rewrite the elements in the field into the form of polynomial，and then perform the operations on Z ₃ according to the polynomial coefficients.Using α ² + α +2=0，we have

α ² =- α -2=2 α +1；

α ³ = αα ² = α （2 α +1）= 2 α ² + α = 5 α +2=2 α +2；

α ⁴ = αα ³ = α （2 α +2）= 2 α ² + 2 α = 6 α +2=2；

α ⁵ = αα ⁴ =2 α ；

α ⁶ = αα ⁵ =2 α ² =4 α +2= α +2；

α ⁷ = αα ⁶ = α （ α +2）= α ² + 2 α = 4 α +1= α +1； α ⁸ = αα ⁷ = α ² + α = 3 α +1=1.

It can be seen that through the power operation of α generates all elements of this field，that is to say， α is the primitive element of GF（9）.In addition，with this example，one can find that the elements in the finite field GF（ p ^m ）can be expressed not only in the form of power，but also in the form of polynomial with the highest degree of m -1.The latter could be further transformed into vector form based on｛1， α ｝.As Table 1.2.1 shows.The additions and multiplications are shown in Figure 1.2.9 and Figure 1.2.10，respectively.

Generally，the polynomial form of GF（ p ^m ）could be expressed by the vector form based on｛1， α ， α ² ，…， α ^{m -1} ｝，which becomes another construction of GF（ p ^m ）.

Theorem 1.2.7 Let f （ x ）be a m -degree primitive polynomial on Z _p .Assume α to be a root in Ω _p .Then the vector space spanned by the base｛0，1， α ， α ² ，…， α ^{pm -2} ｝is a finite field GF（ p ^m ），i.e.，

GF（ p ^m ）=｛ a ₀ + a ₁ α +…+ a _{m -1} α ^{m -1} ， a _i ∈Z _p ｝

This construction also provides us with another way to understand the extended field GF（ p ^m ），that is，GF（ p ^m ）is a m -dimensional vector space based on F _p .Recall that the complex number field C is a two-dimensional vector space based on the real number field R.

Definition 1.2.18（Affine Space） The m -dimensional vector space based on F _p is as

is called a m -dimensional affine space.

Thus，the extension field GF（ p ^m ）is actually the affine space F _p ^m .This viewpoint is very useful for understanding coding，especially for network coding，by mapping the extension field to affine space，or to map the elements in the extension field to vectors in affine space.In network communication，the data packet composed of n symbols is transmitted on the network links.Each symbol is taken from a finite field F _p （mostly GF（2））.Therefore，the data packet can be regarded as a n -dimensional vector based on F _p ，or a symbol in the extended field.Therefore，when performing network coding operation，both the n -dimensional vector operation on F _p and the single symbol operation on F _p ^m can be performed.

The power form of field elements is convenient for multiplication operation，and the polynomial form is convenient for addition calculation.In addition，error correction code mainly uses GF（2）and its extension field，where the vector form is more commonly used.

Digital communication and coding often need operating on F ₂ =（Z ₂ ，+ ₂ ，× ₂ ）.As a kind of finite field F _p ，the properties of F _p are also satisfied for F ₂ .In order to highlight the application of this field in coding，in the following will emphasize on the finite field F ₂ .

The rules of addition and multiplication of GF（2）（i.e.， F ₂ ）are given by Example 1.2.1.Similar to F _p ，polynomials could be defined on GF（2）.A polynomial f （ x ）with coefficients drawn from GF（2）is with the following form.

where a _i ∈GF（2） and a _n ≠0. n is the degree of f （ x ）.Since the coefficient a _i can only take value from 0 or 1，there are at most a number of 2 ⁿ distinct polynomials with degree n .Similar to the polynomial ring，the polynomial on GF（2）can also be added，subtracted，multiplied and divided.The operation rule is that the coefficients of the two polynomials are added，subtracted，multiplied and divided on R .

Let p （ x ）be a m -degree polynomial on GF（2）.If p （ x ）cannot be divided by any other polynomial with degree in（0， m ），then it is called an irreducible polynomial.

Example 1.2.13 x ² + x +1， x ³ + x +1， x ⁴ + x +1 are three irreducible polynomials with the degree of 2，3，4，respectively. x ² +1， x ² + x are not irreducible polynomials because they could be divided by x +1.

Theorem 1.2.8 Any m -degree irreducible polynomial on the field GF（2）can be divided by .

Definition 1.2.19 Let a m -degree irreducible polynomial f （ x ）on the field GF（2）divide x ⁿ -1.If the least number of n =2 ^m -1 in condition that it is divisible，then the irreducible polynomial f （ x ）is called a primitive polynomial.

Example 1.2.14 x ⁴ + x +1 could divide x ¹⁵ +1，but cannot be divided by any x ⁿ +1 1≤ n ＜15，so it is a primitive polynomial. x ⁴ + x ³ + x ² + x +1 is an irreducible polynomial but not a primitive polynomial since it can divide x ⁵ +1.

Theorem 1.2.9 .

Similarly， .

As GF（ p ^m ）could be generated with the extension of Z _p ，GF（2 ^m ）could be constructed from GF（2），which is called the extension field of GF（2）.It is

GF（2 ^m ）=｛0，1， α ， α ² ，…， α ^{2 m -2} ｝

With α being a root of a m -degree polynomial p （ x ）on GF（2），i.e.， p （ α ）=0.The addition and multiplication of GF（2 ^m ）is as follows.

Multiplication 0·0=0·1=1·0=0；1·1=1；1· α = α ·1= α ； α ¹ = α ； α ² = α · α ；

α ³ = α · α · α ；… Because p （ x ）is a m -degree primitive polynomial，we have +1= p （ x ） q （ x ）.Since p （ α ）=0， +1= p （ α ） q （ α ）=0，so =1.

Therefore，GF（2 ^m ）is closed with the multiplication. α is the primitive element and 1 is the multiplication identity.

Addition To define the addition of GF（2 ^m ），we need to use the polynomial form of the elements.Because p （ x ）is a m -degree primitive polynomial，for 0≤ i ≤2 ^m -2，we have

x ⁱ = p （ x ） q _i （ x ）+ r _i ^（ x ）

where the degree of r _i （ x ）is smaller than m -1，i.e.， r _i （ x ）= r _{i 0} + r _{i 1} x + +…+ .

So we have α ⁱ = r _i （ α ）= r _{i 0} + r _{i 1} α + r _{i 2} α ² +…+ r _{i （ m -1）} α ^{m -1} .Moreover，the element 0 in GF（2 ^m ）can be viewed as the polynomial with all coefficients being 0.Thus，every element of GF（2 ^m ）could be expressed by the polynomial form，and the 2 ^m elements in GF（2 ^m ）and 2 ^m polynomials with degree less than or equal to m -1 are one-to-one correspondence.Using polynomial representation，we define the addition on GF（2 ^m ）as

0+ α ⁱ = α ⁱ +0= α ⁱ

α ⁱ + α ^j =（ r _{i 0} + r _{j 0} ）+（ r _{i 1} + r _{j 1} ） α +（ r _{i 2} + r _{j 2} ） α ² +…+（ r _{i （ m -1）} + r _{j （ m -1）} ） α ^{m -1}

According to the closure of polynomial addition on GF（2），we know that GF（2 ^m ）is closed for the addition given above，0 is the addition identity element of addition，and the characteristic of the field is 2.In addition，since the m -tuple polynomial coefficients（ r _{i 0} ， r _{i 1} ， r _{i 2} ，…， r _{i （ m -1）} ）and polynomials are one-to-one correspondence，any element in GF（2 ^m ）can be represented by the m -tuple polynomial coefficients.

GF（2 ^m ）has the following properties.

Theorem 1.2.10 The root of a polynomial on GF（2） ^m ay exist in GF（2 ^m ）.

Theore _m 1.2.11 Let f （ x ）be a polynomial on GF（2）， β ∈GF（2 ^m ）.If β is a root of f （ x ），then for every positive integer n ， is a root of f （ x ）too，which is called the conjugate root of β .

Theorem 1.2.12 A number of 2 ^m -1 non-zero elements｛1， α ， α ² ，…， ｝in GF（2 ^m ）are all roots of the polynomial .

Theorem 1.2.13 A number of 2 ^m elements｛0，1， α ， α ² ，… ｝in GF（2 ^m ）are all roots of the polynomial + x . 45TiGKaqWZ5r79C1vPxocEbjllojaMowo5rvmOBMTEXMmAJ3kOY8P1ooifqfGgvM