primitive polynomial

English

Noun

primitive polynomial (plural primitive polynomials)${\displaystyle }$

1. (algebra, ring theory) A polynomial over an integral domain R such that no noninvertible element of R divides all its coefficients at once; (more specifically) a polynomial over a GCD domain R such that the greatest common divisor of its coefficients equals 1.
   • 1992, T. T. Moh, Algebra, World Scientific, page 124:

     We claim that every primitive polynomial can be written as a product of irreducible elements in $\mathbf {D} [x]$. […] By induction on the degree of the primitive polynomials, we conclude that both $g(x),h(x)$ can be written as product of irreducible elements in $\mathbf {D} [x]$.

   • 2000, David M. Arnold, Abelian Groups and Representations of Finite Partially Ordered Sets, Springer, page 114:

     If $f(x)\in \mathbb {Z} [x]$, the ring of polynomials with coefficients in $\mathbb {Z}$, then the content of $f$, denoted by $c(f)$, is the greatest common divisor of the coefficients of $f$. The polynomial $f(x)$ is called a primitive polynomial if $c(f)=1$. Since $c(fg)=c(f)c(g)$, by Gauss's lemma [Hungerford, 74], the set $S$ of primitive polynomials in $\mathbb {Z} [x]$ is a multiplicatively closed set. Define $\Lambda =\mathbb {Z} [x]_{S}$, the localization of $\mathbb {Z} [x]$ at $S$, a subring of the field of quotients $\mathbb {Q} (x)$ of $\mathbb {Z} [x]$. Elements of $\Lambda$ are of the form $f(x)/g(x)$ with $f(x),g(x)\in \mathbb {Z} [x]$ and $g(x)$ a primitive polynomial.

   • 2000, Jun-ichi Igusa, An Introduction to the Theory of Local Zeta Functions, American Mathematical Society, page 1:

     According to the Gauss lemma, the product of primitive polynomials is primitive. Therefore if $f(x),g(x)$ are primitive and $f(x)=g(x)h(x)$ with $h(x)$ in $F[x]$, then necessarily $h(x)$ is in $A[x]$ and primitive. […] The irreducible elements of $A[x]$ are irreducible elements of $A$ and primitive polynomials which are irreducible in $F[x]$.

2. (algebra, field theory) A polynomial over a given finite field whose roots are primitive elements; especially, the minimal polynomial of a primitive element of said finite field.
   • 2002, Charles E. Stroud, A Designer's Guide to Built-in Self-Test, Kluwer Academic, page 69:

     Primitive polynomials make the initialization of LFSRs a simpler task since any nonzero state guarantees that all non-zero states will be visited in the maximum length sequence.

   • 2003, Zhe-Xian Wan, Lectures on Finite Fields and Galois Rings, World Scientific, page 145:

     Definition 7.2 Let $f(x)$ be a monic polynomial of degree $n$ over $\mathbb {F} _{q}$. If $f(x)$ has a primitive element of $\mathbb {F} _{q^{n}}$ as one of its roots, $f(x)$ is called a primitive polynomial of degree $n$ over $\mathbb {F} _{q}$.
     Theorem 7.7 For any positive integer $n$ there always exist primitive polynomials of degree $n$ over $\mathbb {F} _{q}$. All the $n$ roots of a primitive polynomial of degree $n$ over $\mathbb {F} _{q}$ are primitive elements of $\mathbb {F} _{q^{n}}$. All primitive polynomials of degree $n$ over $\mathbb {F} _{q}$ are irreducible over $\mathbb {F} _{q}$. The number of primitive polynomials of degree $n$ over $\mathbb {F} _{q}$ is equal to $\phi (q^{n}-1)/n$.

   • 2008, Stephen D. Cohen, Mateja Preŝern, “The Hansen-Mullen Primitivity Conjecture: Completion of Proof”, in James McKee, Chris Smyth, editors, Number Theory and Polynomials, Cambridge University Press, page 89:

     This paper completes an efficient proof of the Hansen-Mullen Primitivity Conjecture (HMPC) when n = 5, 6, 7 or 8. The HMPC (1992) asserts that, with some (mostly obvious) exceptions, there exists a primitive polynomial of degree n over any finite field with any coefficient arbitrarily prescribed.

Usage notes

• Since fields are rings, the domain of applicability of the ring theory definition includes that of the one specific to Galois fields. It is thus perfectly feasible for a given instance to be a primitive polynomial in both senses of the term: such is the case, for example, for the minimal polynomial (over a given finite field) of a primitive element (i.e., that has said primitive element as root).
• (polynomial over a finite field whose roots are primitive elements):
  • More precisely, a primitive polynomial over (with coefficients in) $\mathbb {F} _{q}$ of order $n$ has roots that are primitive elements of $\mathbb {F} _{q^{n}}$.
  • Given a primitive element $\alpha \in \mathbb {F} _{q}$, the set of powers $\{1,\alpha ,\dots \alpha ^{n-1}\}$ constitutes a polynomial basis of $\mathbb {F} _{q^{n}}$.
    • In consequence, a primitive polynomial is sometimes defined as a polynomial that generates $\mathbb {F} _{q^{n}}$.

Hyponyms

• (polynomial over an integral domain such that no noninvertible element divides all of its coefficients): monic polynomial

Related terms

• primitive part (of a polynomial)

Translations

polynomial over an integral domain such that no noninvertible element divides all of its coefficients

polynomial over a finite field whose roots are primitive elements

See also

• content (of a polynomial)
• irreducible
• primitivity

Further reading

• Polynomial basis on Wikipedia.Wikipedia
• Gauss's lemma (polynomial) on Wikipedia.Wikipedia
• Polynomial ring on Wikipedia.Wikipedia
• Primitive polynomial on Encyclopedia of Mathematics
• Galois field structure on Encyclopedia of Mathematics
• Primitive Polynomial on Wolfram MathWorld