Field

Definition

Definition 5.26

Commutative ring $F$ with $F^{\ast }=F\setminus \{0\}$ is a field

${\mathbb{Z}}_m$ is a field $⟺$ $m$ is prime ${\mathbb{Z}}_m$ is a field $⟹$ ${\mathbb{Z}}_m$ is a integral domain

Quote

Any finite field of order $p^n$ has characteristic $p$

Section 33 Finite Fields

NOTE

All finite fields must have prime-power order. They are all referred to as the Galois field of order $p^n$, or simply $GF(p^n)$

33.1 Theorem

A First Course in Abstract Algebra, p.300

Let $E$ be a finite extension of degree $n$ over a finite field $F$. If $F$ has $q$ elements, then $E$ has $q^n$ elements

Link to original

For an irreducible polynomial $m(x)$ $GF(p)[x{]}_{m(x)}$ is a field. This field is $GF(p^{deg(m)})$ $deg(m)$ is the degree of this polynomial proof see below

$deg(0)=-\infty$

Definition: irreducible

Definition 5.28

A polynomial $a(x)\in F[x]$ with degree at least $1$ is called irreducible if it is divisible only by constant polynomials and by constant multiples of $a(x)$.

In other words: $f(x)\in F[x]$ irreducible, if $deg(f(x))\ge 1$ and $g(x)|f(x)\to deg(g(x))=0\vee \exists c\in F^{\ast }(g(x)=cf(x))$

Definition: gcd of polynominals

The monic polynomial (leading coefficient is 1) $g(x)$ of largest degree such that $g(x)|a(x)$ and $g(x)|b(x)$ is called the greatest common divisor of $a(x)$ and $b(x)$, denoted $gcd(a(x),b(x))$.

Theorem 5.25

Theorem 5.25

Homomorphism of rings

22.4 The Evaluation Homomorphisms for Field Theory

Define the map ${\varphi }_a:F[x]\to E$ as ${\varphi }_{\alpha }(a_0+a_{1}x+\cdots +a_n{x}^n)=a_0+a_1\alpha +\cdots +a_n{\alpha }^n$ $\varphi$ is a homomorphism because: ${\varphi }_{\alpha }(f(x)+g(x))={\varphi }_{\alpha }(f(x))+{\varphi }_{\alpha }(f(x))$ ${\varphi }_{\alpha }(f(x)g(x))={\varphi }_{\alpha }(f(x)){\varphi }_{\alpha }(f(x))$ If $F$ is a field then $F[x]$ is an integral domain, meaning the polynomial is solvable under factorization.

Link to original

Definition 5.33

$\alpha$ is a root of $a(x)$ $\stackrel{def}{⟺}$ $a(\alpha )=0$

Lemma 5.29

For a field $F$ , $\alpha \in F$ is a root of $a(x)$ $⟺$ $(x-\alpha )|a(x)$

Proof: $⟹$ Let $a(\alpha )=0$ then $a(x)=(x-\alpha )q(x)+r(x)$ and $deg(r(x))<1$ $a(\alpha )=(\alpha -\alpha )q(\alpha )+r(\alpha )$ $⟹0=0\cdot q(\alpha )+r⟹r=0$

Proof: $⟸$ Let $a(x)=(x-\alpha )\cdot b(x)$ Evaluation: $a(\alpha )=(\alpha -\alpha )b(\alpha )=0b(\alpha )=0$

Obeservation

$deg(a(x))=n>-\infty ⟹a$ has at most $n$ roots.

Example

$a(x)=x^p-x\in GF(p)[x]$ $|GF(p{)}^{\ast }|=p-1$, meaning ${\alpha }^p=\alpha$ in $GF(p)$

Therefore, $x^p-x={\prod }_{\alpha \in GF(p)}(x-\alpha )=(x-0)(x-1)(x-2)\dots (x-(p-1))$

Lemma 5.32

Lemma 5.32

A polynomial $a(x)\in F[x]$ of degree at most $d$ is uniquely determined by any $d+1$ values of $a(x)$, i.e., by $a({\alpha }_1),...,a({\alpha }_{d+1})$ for any distinct ${\alpha }_1,...,{\alpha }_{d+1}\in F$ .

NOTE

Note that this Theorem does not apply to the example above. There are only $p$ elements in $\mathrm{GF}(p)$. If you take $d=p$, then $d+1=p+1$, but you cannot find $p+1$ distinct points in $\mathrm{GF}(p)$ (there are only $p$ of them). So the theorem simply does not apply to degree $p$ polynomials over $\mathrm{GF}(p)$.

Proof Consider

$$u_i(x)=\frac{{\prod }_{j\ne i}x-{\alpha }_j}{{\prod }_{j\ne i}{\alpha }_i-{\alpha }_j}$$

$u_i({\alpha }_j)=0$ if $i\ne j$ and $u_i({\alpha }_i)=1$

$$\tilde{a}=\sum _{i=1}^{d+1}a({\alpha }_i)u_i(x)$$

$a({\alpha }_i)=\tilde{a}({\alpha }_i)$ for all $i$

Therefore, $(a(x)-\tilde{a}(x))\in F[x]$ with $degree\le d$ , but $d+1$ roots $⟹a(x)=\tilde{a}(x)$

$F[x{]}_{m(x)}=\{a(x)\in F[x]|deg(a(x))<deg(m(x))\}$, $m(x)$ is irreducible is a field

Side note $|F[x{]}_{m(x)}|=|F{|}^{deg(m(x))}$

Application: ECC

Error-Correcting Codes (ECC)

Example

$m(x)=x^2+x+1\in GF(2)[x]$ irreducible $F[x{]}_{m(x)}=\{0,1,x,1+x\}$ $(x+1{)}^2{\equiv }_{m(x)}x$ $(x+1)x{\equiv }_{m(x)}{x}^2+x{\equiv }_{m(x)}1$

$\mathbb{C}\simeq \mathbb{R}[x{]}_{x^2+1}$ ($x^2+1=0⟺x^2=-1$)