Primitive polynomial over a finite field

Summary

A primitive polynomial over a finite field $\F_q$ is the minimal polynomial of a primitive element of some extension $\F_{q^m}$. With such a polynomial, every nonzero element of $\F_{q^m}$ is a power of one root, which makes multiplication easy to compute. Primitive polynomials over $\F_2$ give linear feedback shift registers of maximal period. This notion differs from the primitive polynomial of ring theory, whose coefficients have no common factor.