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

Jump to: navigation, search

# Field

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

Examples:

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

# Polynomial over a field

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

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

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

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

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