Introduction to Finite Fields Yunghsiang S.Han(韩永祥) School of Electrical Engineering Intelligentization Dongguan University of Technology(东莞理工学院) China E-mail:yunghsiangh@gmail.com
Introduction to Finite Fields Yunghsiang S. Han （韩永祥） School of Electrical Engineering & Intelligentization Dongguan University of Technology (东莞理工学院) China E-mail: yunghsiangh@gmail.com
Y.S.Han Finite fields 1 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 defined 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 defined is called a group if the following conditions are satisfied: 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 School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Finite fields 1 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 defined 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 defined is called a group if the following conditions are satisfied: 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 School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Finite fields 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 satisfies the following condition:for any a and b in G, a*b=b*a. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Finite fields 2 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 satisfies the following condition: for any a and b in G, a ∗ b = b ∗ a. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Finite fields 3 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. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Finite fields 3 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. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Finite fields 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,l},⊕)，where⊕is exclusive-OR operation. The order of a group is the number of elements in the group. ·Additive group:({0,l,2,.,m-1},田)，where m∈Z+,and i田j=i+j mod m. -(i田)田k=i田(田k). -e=0. 一} Yo<i<m,m-i is the inverse of i. -i田j=j田i. Multiplicative group:({1,2,3,...,p-1),),where p is a prime and iij mod p. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Finite fields 4 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 − i 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. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Finite fields 5 Proof:Since p is a prime,gcd(i,p)=1 for all 0p.Then a=g.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. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Finite fields 5 Proof: Since p is a prime, gcd(i, p) = 1 for all 0 < i < p. By Euclid’s 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. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Finite fields 6 Subgroups ·His said to be a subgroup of G if(i)HC G and H≠0.(i)）H is closed under the group operation of G and satisfies all the conditions of a group. Let G=(Q,+andI=(Z,+).Then II is a subgroup of G. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Finite fields 6 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 satisfies all the conditions of a group. • Let G = (Q, +) and H = (Z, +). Then H is a subgroup of G. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Finite fields 7 Fields Let F be a set of elements on which two binary operations, called addition“+”and multiplication“.”,are defined.The set F together with the two binary operations and.is a field if the following conditions are satisfied: 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-10),)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. The order of a field is the number of elements of the field. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Finite fields 7 Fields • Let F be a set of elements on which two binary operations, called addition “+” and multiplication “·”, are defined. The set F together with the two binary operations + and · is a field if the following conditions are satisfied: 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. • The order of a field is the number of elements of the field. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Finite fields A field with finite order is a finite field. a-b=a+(-b),where-b is the additive inverse of b. 。a÷b=a·b1,where b-1 is the multiplicative inverse of b. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Finite fields 8 • A field with finite order is a finite field. • a − b ≡ a + (−b), where −b is the additive inverse of b. • a ÷ b ≡ a · b −1 , where b −1 is the multiplicative inverse of b. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Finite fields 9 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=0anda≠0 imply that b=0. ·a,b∈F,-(a·b)=(-a).b=a(-b). Proof:0=0.6=(a+(-a)).b=a.6+(-a).b.Similarly,we can prove that-(a·b)=a·(-b. Cancellation law:a0 and a.b=a.c imply that b=c. Proof:Since a≠0，a1.(a:b)=a-1.(ac.Hence, (a-1·a)·b=(a-1·a)c,i.e,b=c. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Finite fields 9 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, a −1 · (a · b) = a −1 · (a · c). Hence, (a −1 · a) · b = (a −1 · a) · c, i.e., b = c. School of Electrical Engineering & Intelligentization, Dongguan University of Technology