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

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
imported>Etone
Line 6: Line 6:
!Axioms
!Axioms
|-
|-
|rowspan="9" style="background-color:#ffffcc;"|'''''field'''''
|rowspan="9" style="background-color:#ffffcc;text-align:center;"|'''''field'''''
|rowspan="8" style="background-color:#ffffcc;"|'''''commutative<br>ring'''''
|rowspan="8" style="background-color:#ffffcc;text-align:center;"|'''''commutative<br>ring'''''
|rowspan="7" style="background-color:#ffffcc;"|'''''ring'''''
|rowspan="7" style="background-color:#ffffcc;text-align:center;"|'''''ring'''''
|rowspan="4" style="background-color:#ffffcc;"|'''''abelian<br>group'''''
|rowspan="4" style="background-color:#ffffcc;text-align:center;"|'''''abelian<br>group'''''
|rowspan="3" style="background-color:#ffffcc;"|'''''group'''''
|rowspan="3" style="background-color:#ffffcc;text-align:center;"|'''''group'''''
| rowspan="2" style="background-color:#ffffcc;"|'''''monoid'''''
| rowspan="2" style="background-color:#ffffcc;text-align:center;"|'''''monoid'''''
|style="background-color:#ffffcc;"|'''''semigroup'''''
|style="background-color:#ffffcc;text-align:center;"|'''''semigroup'''''
|rowspan="4" style="text-align:center;"|<math>+</math>
|rowspan="4" style="text-align:center;"|<math>+</math>
|1. '''Addition''' is '''associative''': <math>\forall x,y,z\in S, (x+y)+z= x+(y+z).</math>
|1. '''Addition''' is '''associative''': <math>\forall x,y,z\in S, (x+y)+z= x+(y+z).</math>

Revision as of 16:22, 13 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 Operations Axioms
field commutative
ring
ring abelian
group
group monoid semigroup [math]\displaystyle{ + }[/math] 1. Addition is associative: [math]\displaystyle{ \forall x,y,z\in S, (x+y)+z= x+(y+z). }[/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]
[math]\displaystyle{ +,\cdot }[/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]
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: For any integer [math]\displaystyle{ n\gt 1 }[/math], the modulo ring [math]\displaystyle{ \mathbb{Z}_n=\{0,1,\ldots,n-1\} }[/math] (where addition [math]\displaystyle{ + }[/math] and multiplication [math]\displaystyle{ \cdot }[/math] are defined modulo [math]\displaystyle{ n }[/math]) is a commutative ring. 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. Sometimes, [math]\displaystyle{ \mathbb{Z}_p }[/math] as a field is also denoted as [math]\displaystyle{ \mathbb{Z}/p\mathbb{Z} }[/math] or [math]\displaystyle{ \mathsf{GF}(p) }[/math].

A finite field of order [math]\displaystyle{ q }[/math] (which means the size of the finite set [math]\displaystyle{ S }[/math] is [math]\displaystyle{ q }[/math]) is usually written as [math]\displaystyle{ \mathsf{GF}(q) }[/math], called the Galois field of order [math]\displaystyle{ q }[/math].