高级算法 (Fall 2019)/Finite Field Basics

From EtoneWiki
Jump to: navigation, search

Field

Let [math]S[/math] be a set, closed under binary operations [math]+[/math] (addition) and [math]\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]\forall x,y,z\in S, (x+y)+z= x+(y+z).[/math] [math]+[/math]
2. Existence of additive identity 0: [math]\forall x\in S, x+0= 0+x=x.[/math]
3. Everyone has an additive inverse: [math]\forall x\in S, \exists -x\in S, \text{ s.t. } x+(-x)= (-x)+x=0.[/math]
4. Addition is commutative: [math]\forall x,y\in S, x+y= y+x.[/math]
5. Multiplication distributes over addition: [math]\forall x,y,z\in S, x\cdot(y+z)= x\cdot y+x\cdot z[/math] and [math](y+z)\cdot x= y\cdot x+z\cdot x.[/math] [math]+,\cdot[/math]
6. Multiplication is associative: [math]\forall x,y,z\in S, (x\cdot y)\cdot z= x\cdot (y\cdot z).[/math] [math]\cdot[/math]
7. Existence of multiplicative identity 1: [math]\forall x\in S, x\cdot 1= 1\cdot x=x.[/math]
8. Multiplication is commutative: [math]\forall x,y\in S, x\cdot y= y\cdot x.[/math]
9. Every non-zero element has a multiplicative inverse: [math]\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](S,+)[/math], and the ring, commutative ring, and field are given by [math](S,+,\cdot)[/math].

Examples:

  • Infinite fields: [math]\mathbb{Q}[/math], [math]\mathbb{R}[/math], [math]\mathbb{C}[/math] are fields. The integer set [math]\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]q[/math], is usually denoted as [math]\mathsf{GF}(q)[/math] or [math]\mathbb{F}_q[/math].
    • Prime field [math]{\mathbb{Z}_p}[/math]: For any integer [math]n\gt 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 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]
    • 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
A finite field of order [math]q[/math] exists if and only if [math]q=p^k[/math] for some prime number [math]p[/math] and positive integer [math]k[/math]. Moreover, all fields of a given order are isomorphic.

Polynomial over a field

Given a field [math]\mathbb{F}[/math], the polynomial ring [math]\mathbb{F}[x][/math] consists of all polynomials in the variable [math]x[/math] with coefficients in [math]\mathbb{F}[/math]. Addition and multiplication of polynomials are naturally defined by applying the distributive law and combining like terms.

Proposition (polynomial ring)
[math]\mathbb{F}[x][/math] is a ring.

The degree [math]\mathrm{deg}(f)[/math] of a polynomial [math]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]\mathbb{F}[x][/math] is a ring, we cannot do division the way we do it in a field like [math]\mathbb{R}[/math], but we can do division the way we do it in a ring like [math]\mathbb{Z}[/math], leaving a remainder. The equivalent of the integer division for [math]\mathbb{Z}[/math] is as follows.

Proposition (division for polynomials)
Given a polynomial [math]f[/math] and a nonzero polynomial [math]g[/math] in [math]\mathbb{F}[x][/math], there are unique polynomials [math]q[/math] and [math]r[/math] such that [math]f =q\cdot g+r[/math] and [math]\mathrm{deg}(r)\lt \mathrm{deg}(g)[/math].

The proof of this is by induction on [math]\mathrm{deg}(f)[/math], with the basis [math]\mathrm{deg}(f)\lt \mathrm{deg}(g)[/math], in which case the theorem holds trivially by letting [math]q=0[/math] and [math]r=f[/math].

As we turn [math]\mathbb{Z}[/math] (a ring) into a finite field [math]\mathbb{Z}_p[/math] by taking quotients [math]\bmod p[/math], we can turn a polynomial ring [math]\mathbb{F}[x][/math] into a finite field by taking [math]\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]f[/math] that cannot be factored as [math]f=g\cdot h[/math] for any non-constant polynomials [math]g[/math] and [math]h[/math].