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 .
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.