Classification of Finite Fields
Theorem.
For every finite field \(K\) there exists a prime number \(p\) and natural number \(n \ge 1\) such that \(K\) has \(p^n\) elements. All fields with this number of elements are isomorphic.
Construction of Finite Fields
Proposition.
For a field \(K\) and irreducible polynom \(f \in K[x]\) the factor ring \(L := K[x]/(f)\) is a field. \(K\) can be embedded in \(L\) isomorphically and \(L\) is a \(\operatorname{degree}(f)\) dimensional vector space over this embedding.
Proposition.
For every prime number \(p\) the ring of integers modulo \(p\) is the finite field with \(p\) elements. It is denoted by \(\mathbb{Z}_p\).
For every \(k \ge 1\) there exists a irreducible polynom \(f \in \mathbb{Z}_p[x]\) of degree \(k\).
All normed and irreducible factors of \(x^{p^n} - x\) are precisely the irreducible and normed polynoms in \(\mathbb{Z}_p[x]\) which have degree that divides \(n\).
The addition group is isomporphic to \(C_p^n\), where \(C_p\) is the integer addition group modulo \(p\).
The multiplication group is isomporphic to \(C_{p^n}\) which means there is one generating element.
Implementation
So the main task is to find a irreducible polynom over \(\mathbb{Z}_p[x]\) of degree \(n\). The approach was to iterate over all normed polynoms \(f\) of degree \(n\) and check if they divide \(x^{p^n} - x\). As all irreducible factors of \(f\) are also irreducible factors of \(x^{p^n} - x\), to check irreducibility of \(f\) it is sufficient to check polynoms with degree that divides \(n\).
To implement the polynomial modular arithmetic following Euclids algorithm was used: \[ \begin{align*} & \text{Polynoms } p, q \text{ with degrees } n \ge m \text{ respectively}\\ & \text{Calculate} \quad p \mod q:\\ & \text{while} \quad\operatorname{degree}(p) \ge \operatorname{degree}(q) \\ &\quad \quad p = p - \frac{p_n}{q_m} q \\ & \text{return } p \end{align*} \] where \(p_n\) and \(q_m\) are the highest non zero coefficients of \(p\) and \(q\) respectively.
Code at my GitHub.