2.10 Finite fields

In this section, we will delve into the study of finite fields, which play a key role in cryptography.

Proposition 2.10.1: The characteristic of finite field

$$\begin{align*} &\sphericalangle \\ &F \in \mathcal F \\ &|F| < \infty\\ &\text{char }F = p \\ \hline \\ &p \in \mathfrak P \end{align*}$$

Proof

Remember that by $(2.4.5)$ each field has either prime or zero characteristic. Obviously finite fields cannot have zero characteristic so $p \in \mathfrak P$.

$\square$

Proposition 2.10.2: The order of finite field

$$\begin{align*} &\sphericalangle \\ &F \in \mathcal F \\ &|F| < \infty\\ &\text{char }F = p \\ \hline \\ &\begin{align*} &\exists F' \subseteq F: F' \cong_F \mathbb F_p \hspace{0.5cm} \tag{a}\\ &|F|=p^n, n \in \N \hspace{0.5cm} \tag{b}\\ \end{align*} & \end{align*}$$

Proof

a., b.

Define $\phi: \Z \rightsquigarrow_R F, n \mapsto \underbrace{1 + 1 + \ldots + 1}_{n\text{ times}}$ (it's easy to check that this is indeed a ring homomorphism). Then $\ker \phi = p\Z$. So by $(2.3.9)$ we have $\mathbb F_p=\Z/p\Z \cong_R \phi(\Z) \subseteq F$ and $\phi(1)=1$. Denote $F':=\phi(\Z)$. Since $F$ is finite $[F:F'] = n < \infty$ for some $n$. Finally if we count all vectors in $F$ over $F'$ then it will be exactly $p^n$.

$\square$

def: Frobenius endomorphism

$$\begin{align*} &\sphericalangle \\ &F \in \mathcal F \\ &\text{char } F= p \\ &\rho^k: F \to F, x \mapsto x^{p^k} \\ \hline \\ &\rho^k - \text{Frobenius endomorphism} \\ \end{align*}$$

note

It's easy to see that $\rho^{m+n}=\rho^{m}\rho^{n}$

note

We'll prove that this is indeed a homomorphism below

Proposition 2.10.3: Frobenius action on polynomials

$$\begin{align*} &\sphericalangle \\ &F \in \mathcal F \\ &\text{char } F= p \\ &p(x_1, \ldots, x_n) \in F[x_1, \ldots, x_n] \\ \hline \\ &\rho^k(p(a_1, \ldots, a_n))=p^{\rho^k}(\rho^k(a_1), \ldots, \rho^k(a_n)), a_i \in F \end{align*}$$

Proof

Notice that in $\rho^k(p(a_1, \ldots, a_n))=(\sum_i b_i a_1^{d_{1, i}} \cdot \ldots \cdot a_{k_i}^{d_{k_i, i}})^{p^k}$ any cross term will have a factor of $p^k$ but $\text{char }F = p$, so $p^k=0$ in $F$. So any cross-term will be $0$ and we finish the proof.

$\square$

Proposition 2.10.5: Finite field as extension of $\mathbb F_p$

$$\begin{align*} &\sphericalangle \\ &F \in \mathcal F \\ &|F| = p^n \\ \hline \\ &\begin{align*} &F \cong \mathbb F_p(\parallel x^{p^n}-x) \hspace{0.5cm} \tag{a}\\ &F/_{\text{Gal}} \mathbb F_p \hspace{0.5cm} \tag{b}\\ & \text{Gal}(F/\mathbb F_p) = \lang \rho \rang_G \hspace{0.5cm} \tag{c}\\ & |\text{Gal}(F/\mathbb F_p)| = n \hspace{0.5cm} \tag{d}\\ \end{align*} \end{align*}$$

Proof

a.

Consider $|F^*|=p^n-1$ and some $a \in F^*$. Since $|\lang a \rang_{(G, \cdot)}| \mid |F^*|= p^n-1$ we know that $a^{p^n-1}=1$ or $a^{p^n}=a$. Note that this equation holds for $a=0$ as well, so the polynomial $p(x)=x^{p^n}-x$ has exactly $p^n$ roots, each root is a distinct element from $F$.

By $(2.4.5)$ the characteristic is either prime or $0$. Obviously it cannot be $0$ and since characteristic is the additive order of $1$ it must divide $p^n$ so $\text{char } F = p$. So by $(2.10.2.a)$ we have some $F' \subseteq F, F' \cong \mathbb F_p$.

Finally using theorem $(2.8.11)$ with $F_1=\mathbb F_p, F_2=F', p = x^{p^n}-x$ we finish the proof.

b.

$F=\mathbb F_p(\parallel x^{p^n}-x)$ so by definition $F/_\lhd \mathbb F_p$. From $(a)$ it has disctinct roots so $F/_\boxminus \mathbb F_p$. By $(2.9.15)$ we have $F/_{\text{Gal}} \mathbb F_p$.

c.

To prove that $\rho \in \text{End}_F(F)$, take $p_1(x,y)=x+y$ and $p_2(x,y)=xy$ and apply $(2.10.3)$. Also obviously $\rho(1)=1$.

By Fermat's little theorem $(2.2.10)$ $\forall a \in \mathbb F_p: \rho(a)=a$. By $(2.4.20.c)$ we know that $\rho$ is injective and since $|F| < \infty$ it's also surjective. So $\rho \in \text{Gal}(F/\mathbb F_p)$.

Denote $p(x)=x^p-x$ then $\{a \in F: p(a)=0\} = \text{Fix}_\rho(F) \supseteq \mathbb F_p$. But $p(x)$ has no more than $p$ roots so $\text{Fix}_\rho(F) = \mathbb F_p$. So each power of $\rho$ fixes exactly $\mathbb F_p$ or we can write $\text{Fix}_{\lang \rho \rang_G}(F)=\mathbb F_p$ By the Fundametal theorem of Galois theory $(2.9.16)$ $\lang \rho \rang_G = \text{Gal}(F/\mathbb F_p)$.

d.

$(2.9.16) \implies n=[F:\mathbb F_p] = |\text{Gal}(F/\mathbb F_p)|$

$\square$

Proposition 2.10.6: Finite field of a certain order is unique

$$\begin{align*} &\sphericalangle \\ &F_1, F_2 \in \mathcal F \\ &|F_1|=|F_2|=p^n \\ \hline \\ &F_1 \cong F_2 \end{align*}$$

Proof

By $(2.10.5)$ $F_1 \cong \mathbb F_p(\parallel x^{p^n}-x) \cong F_2$

$\square$

note

We'll denote the finite field of order $p^n$ by $\mathbb F_{p^n}$.

Corrolary 2.10.7: Finite field is perfect

$$\begin{align*} &\sphericalangle \\ &F \in \mathcal F \\ &|F|=p^n \\ \hline \\ &F \in \mathcal F^{\mathcal P} \end{align*}$$

Proof

Since $\rho \in \text{Gal}(F/\mathbb F_p)$ we have $F^p=F$ (note that it means that the sets are the same, not that $\forall x \in F: \rho(x)=x$). By $(2.9.12)$ we finish the proof.

$\square$

Proposition 2.10.8: Finite subfield order

$$\begin{align*} &\sphericalangle \\ &F, E \in \mathcal F \\ &|F| = p^m \\ &|E| = p^n \\ \hline \\ &E/F \iff m \mid n \end{align*}$$

Proof

$\implies$

We have $E/F/\mathbb F_p$ so $[E:\mathbb F_p]=[E: F][F:\mathbb F_p] \implies n=[E:F]m \implies m \mid n$

$\impliedby$

$m \mid n \implies p^n-1=(p^m)^k-1=(p^m-1)((p^m)^{k-1}+\ldots+1) \implies p^m-1 \mid p^n-1 \overset{\text{take }y=x^{p^m-1}}\implies x^{p^m-1}-1 \mid x^{p^n-1}-1 \implies x^{p^m}-x \mid x^{p^n}-x$

So we have $E=\mathbb F_p(\parallel P_1), F=\mathbb F_p(\parallel P_2), P_1 \supseteq P_2 \implies E/F$

$\square$

Proposition 2.10.9: Subgroup of multiplicative group is cyclic

$$\begin{align*} &\sphericalangle \\ &F \in \mathcal F \\ &G \subseteq_G F^* \\ \hline \\ &G \in \mathcal G^{\circlearrowleft} \end{align*}$$

Proof

By $(2.2.38)$ we have:

$$G \cong \Z_{p_{1}^{\alpha_1}} \times \ldots \times \Z_{p_{k}^{\alpha_k}}$$

Where $p_i$ are primes, not necessary different. Let's pick from each $\Z_{p_i^{\alpha_i}}$ it's generator $a_i$ and make element $a=(a_1, \ldots, a_n)$ it's order will be $m:=\text{LCM}(p_1^{\alpha_1}, \ldots, p_k^{\alpha_k})$. Note that $m \le |G|$ since obviously each $p_1^{\alpha_1} \mid |G|$. On the other hand each $g=(g_1, \ldots, g_n) \in G$ we have $g^r - 1 = 0, r \mid m$ because it's order is $\text{LCM}(\text{ord }g_1, \ldots, \text{ord }g_n)=\text{LCM}(p_1^{\alpha_1-\beta_1}, \ldots, p_n^{\alpha_n-\beta_n})$. So every $g \in G$ satisfies $x^m-1=0$ that has no more than $m$ roots so $|G|\leq m$.

So we have $|G|=m$ and so $\lang a \rang_G=G$

$\square$