高级算法 (Fall 2017)/Finite Field Basics: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
No edit summary
imported>Etone
No edit summary
Line 47: Line 47:
** '''Prime field''' <math>{\mathbb{Z}_p}</math>: For any integer <math>n>1</math>,  <math>\mathbb{Z}_n=\{0,1,\ldots,n-1\}</math> under modulo-<math>p</math> addition <math>+</math> and multiplication <math>\cdot</math> forms a commutative ring. It is called '''quotient ring''', and is sometimes denoted as <math>\mathbb{Z}/n\mathbb{Z}</math>.  In particular, for '''prime''' <math>p</math>, <math>\mathbb{Z}_p</math> is a field. This can be verified by [http://en.wikipedia.org/wiki/Fermat%27s_little_theorem Fermat's little theorem].
** '''Prime field''' <math>{\mathbb{Z}_p}</math>: For any integer <math>n>1</math>,  <math>\mathbb{Z}_n=\{0,1,\ldots,n-1\}</math> under modulo-<math>p</math> addition <math>+</math> and multiplication <math>\cdot</math> forms a commutative ring. It is called '''quotient ring''', and is sometimes denoted as <math>\mathbb{Z}/n\mathbb{Z}</math>.  In particular, for '''prime''' <math>p</math>, <math>\mathbb{Z}_p</math> is a field. This can be verified by [http://en.wikipedia.org/wiki/Fermat%27s_little_theorem Fermat's little theorem].
** '''Boolean arithmetics''' <math>\mathsf{GF}(2)</math>: The finite field of order 2 <math>\mathsf{GF}(2)</math> contains only two elements 0 and 1, with bit-wise XOR as addition and bit-wise AND as multiplication. <math>\mathsf{GF}(2^n)</math>
** '''Boolean arithmetics''' <math>\mathsf{GF}(2)</math>: The finite field of order 2 <math>\mathsf{GF}(2)</math> contains only two elements 0 and 1, with bit-wise XOR as addition and bit-wise AND as multiplication. <math>\mathsf{GF}(2^n)</math>
** Other examples: There are other examples of finite fields, for instance <math>\{a+bi\mid a,b\in \mathbb{Z}_3\}</math> where <math>I=\sqrt{-1}</math>. This field is isomorphic to <math>\mathsf{GF}(9)</math>. In fact, a finite field of order <math>q</math> exists if and only if <math>q</math> is a prime power <math>p^k</math> (where <math>p</math> is a prime number and <math>k</math> is a positive integer). Moreover, all fields of a given order are isomorphic.
** Other examples: There are other examples of finite fields, for instance <math>\{a+bi\mid a,b\in \mathbb{Z}_3\}</math> where <math>I=\sqrt{-1}</math>. This field is isomorphic to <math>\mathsf{GF}(9)</math>. In fact, the following theorem holds for finite fields of given order.
 
{{Theorem|Theorem|
:A finite field of order <math>q</math> exists if and only if <math>q</math> is a prime power <math>p^k</math> (where <math>p</math> is a prime number and <math>k</math> is a positive integer). Moreover, all fields of a given order are isomorphic.
}}

Revision as of 05:03, 15 September 2017

Field

Let [math]\displaystyle{ S }[/math] be a set, closed under two binary operations [math]\displaystyle{ + }[/math] (addition) and [math]\displaystyle{ \cdot }[/math] (multiplication). It gives us the following algebraic structures if the corresponding set of axioms are satisfied.

Structures Axioms Operations
field commutative
ring
ring abelian
group
group monoid semigroup 1. Addition is associative: [math]\displaystyle{ \forall x,y,z\in S, (x+y)+z= x+(y+z). }[/math] [math]\displaystyle{ + }[/math]
2. Existence of additive identity 0: [math]\displaystyle{ \forall x\in S, x+0= 0+x=x. }[/math]
3. Everyone has an additive inverse: [math]\displaystyle{ \forall x\in S, \exists -x\in S, \text{ s.t. } x+(-x)= (-x)+x=0. }[/math]
4. Addition is commutative: [math]\displaystyle{ \forall x,y\in S, x+y= y+x. }[/math]
5. Multiplication distributes over addition: [math]\displaystyle{ \forall x,y,z\in S, x\cdot(y+z)= x\cdot y+x\cdot z }[/math] and [math]\displaystyle{ (y+z)\cdot x= y\cdot x+z\cdot x. }[/math] [math]\displaystyle{ +,\cdot }[/math]
6. Multiplication is associative: [math]\displaystyle{ \forall x,y,z\in S, (x\cdot y)\cdot z= x\cdot (y\cdot z). }[/math] [math]\displaystyle{ \cdot }[/math]
7. Existence of multiplicative identity 1: [math]\displaystyle{ \forall x\in S, x\cdot 1= 1\cdot x=x. }[/math]
8. Multiplication is commutative: [math]\displaystyle{ \forall x,y\in S, x\cdot y= y\cdot x. }[/math]
9. Every non-zero element has a multiplicative inverse: [math]\displaystyle{ \forall x\in S\setminus\{0\}, \exists x^{-1}\in S, \text{ s.t. } x\cdot x^{-1}= x^{-1}\cdot x=1. }[/math]

The semigroup, monoid, group and abelian group are given by [math]\displaystyle{ (S,+) }[/math], and the ring, commutative ring, and field are given by [math]\displaystyle{ (S,+,\cdot) }[/math].

Examples:

  • Infinite fields: [math]\displaystyle{ \mathbb{Q} }[/math], [math]\displaystyle{ \mathbb{R} }[/math], [math]\displaystyle{ \mathbb{C} }[/math] are fields. The integer set [math]\displaystyle{ \mathbb{Z} }[/math] is a commutative ring but is not a field.
  • Finite fields: Finite fields are called Galois fields. The number of elements of a finite field is called its order. A finite field of order [math]\displaystyle{ q }[/math], is denoted as [math]\displaystyle{ \mathsf{GF}(q) }[/math].
    • Prime field [math]\displaystyle{ {\mathbb{Z}_p} }[/math]: For any integer [math]\displaystyle{ n\gt 1 }[/math], [math]\displaystyle{ \mathbb{Z}_n=\{0,1,\ldots,n-1\} }[/math] under modulo-[math]\displaystyle{ p }[/math] addition [math]\displaystyle{ + }[/math] and multiplication [math]\displaystyle{ \cdot }[/math] forms a commutative ring. It is called quotient ring, and is sometimes denoted as [math]\displaystyle{ \mathbb{Z}/n\mathbb{Z} }[/math]. In particular, for prime [math]\displaystyle{ p }[/math], [math]\displaystyle{ \mathbb{Z}_p }[/math] is a field. This can be verified by Fermat's little theorem.
    • Boolean arithmetics [math]\displaystyle{ \mathsf{GF}(2) }[/math]: The finite field of order 2 [math]\displaystyle{ \mathsf{GF}(2) }[/math] contains only two elements 0 and 1, with bit-wise XOR as addition and bit-wise AND as multiplication. [math]\displaystyle{ \mathsf{GF}(2^n) }[/math]
    • Other examples: There are other examples of finite fields, for instance [math]\displaystyle{ \{a+bi\mid a,b\in \mathbb{Z}_3\} }[/math] where [math]\displaystyle{ I=\sqrt{-1} }[/math]. This field is isomorphic to [math]\displaystyle{ \mathsf{GF}(9) }[/math]. In fact, the following theorem holds for finite fields of given order.
Theorem
A finite field of order [math]\displaystyle{ q }[/math] exists if and only if [math]\displaystyle{ q }[/math] is a prime power [math]\displaystyle{ p^k }[/math] (where [math]\displaystyle{ p }[/math] is a prime number and [math]\displaystyle{ k }[/math] is a positive integer). Moreover, all fields of a given order are isomorphic.