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