高级算法 (Fall 2018)/Finite Field Basics
Field
Let [math]\displaystyle{ S }[/math] be a set, closed under 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 usually denoted as [math]\displaystyle{ \mathsf{GF}(q) }[/math] or [math]\displaystyle{ \mathbb{F}_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=p^k }[/math] for some prime number [math]\displaystyle{ p }[/math] and positive integer [math]\displaystyle{ k }[/math]. Moreover, all fields of a given order are isomorphic.
Polynomial over a field
Given a field [math]\displaystyle{ \mathbb{F} }[/math], the polynomial ring [math]\displaystyle{ \mathbb{F}[x] }[/math] consists of all polynomials in the variable [math]\displaystyle{ x }[/math] with coefficients in [math]\displaystyle{ \mathbb{F} }[/math]. Addition and multiplication of polynomials are naturally defined by applying the distributive law and combining like terms.
Proposition (polynomial ring) - [math]\displaystyle{ \mathbb{F}[x] }[/math] is a ring.
The degree [math]\displaystyle{ \mathrm{deg}(f) }[/math] of a polynomial [math]\displaystyle{ f\in \mathbb{F}[x] }[/math] is the exponent on the leading term, the term with a nonzero coefficient that has the largest exponent.
Because [math]\displaystyle{ \mathbb{F}[x] }[/math] is a ring, we cannot do division the way we do it in a field like [math]\displaystyle{ \mathbb{R} }[/math], but we can do division the way we do it in a ring like [math]\displaystyle{ \mathbb{Z} }[/math], leaving a remainder. The equivalent of the integer division for [math]\displaystyle{ \mathbb{Z} }[/math] is as follows.
Proposition (division for polynomials) - Given a polynomial [math]\displaystyle{ f }[/math] and a nonzero polynomial [math]\displaystyle{ g }[/math] in [math]\displaystyle{ \mathbb{F}[x] }[/math], there are unique polynomials [math]\displaystyle{ q }[/math] and [math]\displaystyle{ r }[/math] such that [math]\displaystyle{ f =q\cdot g+r }[/math] and [math]\displaystyle{ \mathrm{deg}(r)\lt \mathrm{deg}(g) }[/math].
The proof of this is by induction on [math]\displaystyle{ \mathrm{deg}(f) }[/math], with the basis [math]\displaystyle{ \mathrm{deg}(f)\lt \mathrm{deg}(g) }[/math], in which case the theorem holds trivially by letting [math]\displaystyle{ q=0 }[/math] and [math]\displaystyle{ r=f }[/math].
As we turn [math]\displaystyle{ \mathbb{Z} }[/math] (a ring) into a finite field [math]\displaystyle{ \mathbb{Z}_p }[/math] by taking quotients [math]\displaystyle{ \bmod p }[/math], we can turn a polynomial ring [math]\displaystyle{ \mathbb{F}[x] }[/math] into a finite field by taking [math]\displaystyle{ \mathbb{F}[x] }[/math] modulo a "prime-like" polynomial, using the division of polynomials above.
Definition (irreducible polynomial) - An irreducible polynomial, or a prime polynomial, is a non-constant polynomial [math]\displaystyle{ f }[/math] that cannot be factored as [math]\displaystyle{ f=g\cdot h }[/math] for any non-constant polynomials [math]\displaystyle{ g }[/math] and [math]\displaystyle{ h }[/math].