Polynomials over a prime field

How it works

Polynomials with coefficients in $\mathbb{F}_p$ behave much like whole numbers. They can be added and multiplied coefficientwise modulo $p$, and divided with remainder: for $g \ne 0$ there are unique $q$ and $r$ with $f = qg + r$ and $\deg r < \deg g$. Long division finds them by repeatedly cancelling the leading term, which needs only the inverse of the leading coefficient of $g$, so $p$ must be prime.

With division comes Euclid’s algorithm, and the greatest common divisor, normalized to be monic. The extended algorithm also gives $u$ and $v$ with $uf + vg = \gcd(f, g)$; when the gcd is 1, $u$ is the inverse of $f$ modulo $g$.

If $g$ is irreducible of degree $n$, the residues modulo $g$ form the finite field $\mathbb{F}_{p^n}$, and every non-zero element has such an inverse. This is how $\mathrm{GF}(2^8)$ in AES and the binary fields of some elliptic curves are built, and polynomial rings modulo $x^n + 1$ are the setting of lattice schemes such as Kyber.