finite fields

Work in Progress

Summary

A field is a commutative ring whose nonzero elements are invertible. Quotienting by an irreducible degree- polynomial produces the finite field .

Concept

A commutative ring has an abelian additive group, associative and commutative multiplication with identity, and distributivity. A field additionally gives every nonzero element a multiplicative inverse.

Polynomial division over a field gives

Thus has unique representatives of degree below and is a -dimensional vector space over .

Theorem. is a field iff is irreducible over .

If is irreducible and , then . Polynomial EEA gives such that

so is the inverse of . If is reducible, then the nonzero residue classes of and multiply to zero, so the quotient cannot be a field.

For , the quotient has elements. Every finite field is isomorphic to one of this form, and is cyclic of order . Quadratic residues and DLOG therefore extend from prime fields to all odd finite fields.

Application

If

then . Multiplication by is a companion matrix, and multiplication by any polynomial is the corresponding polynomial in that matrix. This representation leads directly to module LWE.

Related prerequisites: rings, fields, and modular arithmetic.