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

Field

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

The semigroup, monoid, group and abelian group are given by $(S,+)$, and the ring, commutative ring, and field are given by $(S,+,\cdot )$.

Examples:

• Infinite fields: $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$ are fields. The integer set $\mathbb{Z}$ 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 $q$, is usually denoted as $\mathsf{G}\mathsf{F}(q)$ or ${\mathbb{F}}_q$.
  • Prime field ${\mathbb{Z}}_p$: For any integer $n>1$, ${\mathbb{Z}}_n=\{0,1,\dots ,n-1\}$ under modulo-$p$ addition $+$ and multiplication $\cdot$ forms a commutative ring. It is called quotient ring, and is sometimes denoted as $\mathbb{Z}/n\mathbb{Z}$. In particular, for prime $p$, ${\mathbb{Z}}_p$ is a field. This can be verified by Fermat's little theorem.
  • Boolean arithmetics $\mathsf{G}\mathsf{F}(2)$: The finite field of order 2 $\mathsf{G}\mathsf{F}(2)$ contains only two elements 0 and 1, with bit-wise XOR as addition and bit-wise AND as multiplication. $\mathsf{G}\mathsf{F}(2^n)$
  • Other examples: There are other examples of finite fields, for instance $\{a+bi\mid a,b\in {\mathbb{Z}}_3\}$ where $I=\sqrt{-1}$. This field is isomorphic to $\mathsf{G}\mathsf{F}(9)$. In fact, the following theorem holds for finite fields of given order.

Theorem

A finite field of order $q$ exists if and only if $q=p^k$ for some prime number $p$ and positive integer $k$. Moreover, all fields of a given order are isomorphic.

Polynomial over a field

Given a field $\mathbb{F}$, the polynomial ring $\mathbb{F}[x]$ consists of all polynomials in the variable $x$ with coefficients in $\mathbb{F}$. Addition and multiplication of polynomials are naturally defined by applying the distributive law and combining like terms. The degree $\mathrm{d}\mathrm{e}\mathrm{g}(f)$ of a polynomial $f\in \mathbb{F}[x]$ is the exponent on the leading term, the term with a nonzero coefficient that has the largest exponent.

Because $\mathbb{F}[x]$ is a ring, we cannot do division the way we do it in a field like $\mathbb{R}$, but we can do division the way we do it in a ring like $\mathbb{Z}$, leaving a remainder. The equivalent of the integer division for $\mathbb{Z}$ is as follows.

Proposition (division for polynomials)

Given a polynomial $f$ and a nonzero polynomial $g$ in $\mathbb{F}[x]$, there are unique polynomials $q$ and $r$ such that $f=q\cdot g+r$ and $\mathrm{d}\mathrm{e}\mathrm{g}(r)<\mathrm{d}\mathrm{e}\mathrm{g}(g)$.

The proof of this is by induction on $\mathrm{d}\mathrm{e}\mathrm{g}(f)$, with the basis $\mathrm{d}\mathrm{e}\mathrm{g}(f)<\mathrm{d}\mathrm{e}\mathrm{g}(g)$, in which case the theorem holds trivially by letting $q=0$ and $r=f$.

As we turn $\mathbb{Z}$ (a ring) into a finite field ${\mathbb{Z}}_p$ by taking quotients $modp$, we can turn a polynomial ring $\mathbb{F}[x]$ into a finite field by taking $\mathbb{F}[x]$ modulo a "prime-like" polynomial, using the division of polynomials above.

Definition (irreducible polynomial)

A non-constant polynomial $f$ is an irreducible polynomial, or a prime polynomial, if $f$ cannot be factored as $f=g\cdot h$ for any non-constant polynomials $g$ and $h$.