primitive polynomial

English

English Wikipedia has an article on:

Primitive polynomial

Wikipedia

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 ${\displaystyle \mathbf {D} }$. […] By induction on the degree of the primitive polynomials, we conclude that both ${\displaystyle g(x),h(x)}$ can be written as product of irreducible elements in ${\displaystyle \mathbf {D} }$.

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

     If ${\displaystyle f(x)\in \mathbb {Z} }$, the ring of polynomials with coefficients in ${\displaystyle \mathbb {Z} }$, then the content of ${\displaystyle f}$, denoted by ${\displaystyle c(f)}$, is the greatest common divisor of the coefficients of ${\displaystyle f}$. The polynomial ${\displaystyle f(x)}$ is called a primitive polynomial if ${\displaystyle c(f)=1}$. Since ${\displaystyle c(fg)=c(f)c(g)}$, by Gauss's lemma [Hungerford, 74], the set ${\displaystyle S}$ of primitive polynomials in ${\displaystyle \mathbb {Z} }$ is a multiplicatively closed set. Define ${\displaystyle \Lambda =\mathbb {Z} _{S}}$, the localization of ${\displaystyle \mathbb {Z} }$ at ${\displaystyle S}$, a subring of the field of quotients ${\displaystyle \mathbb {Q} (x)}$ of ${\displaystyle \mathbb {Z} }$. Elements of ${\displaystyle \Lambda }$ are of the form ${\displaystyle f(x)/g(x)}$ with ${\displaystyle f(x),g(x)\in \mathbb {Z} }$ and ${\displaystyle 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 ${\displaystyle f(x),g(x)}$ are primitive and ${\displaystyle f(x)=g(x)h(x)}$ with ${\displaystyle h(x)}$ in ${\displaystyle F}$, then necessarily ${\displaystyle h(x)}$ is in ${\displaystyle A}$ and primitive. […] The irreducible elements of ${\displaystyle A}$ are irreducible elements of ${\displaystyle A}$ and primitive polynomials which are irreducible in ${\displaystyle F}$.

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 ${\displaystyle f(x)}$ be a monic polynomial of degree ${\displaystyle n}$ over ${\displaystyle \mathbb {F} _{q}}$. If ${\displaystyle f(x)}$ has a primitive element of ${\displaystyle \mathbb {F} _{q^{n}}}$ as one of its roots, ${\displaystyle f(x)}$ is called a primitive polynomial of degree ${\displaystyle n}$ over ${\displaystyle \mathbb {F} _{q}}$.
     Theorem 7.7 For any positive integer ${\displaystyle n}$ there always exist primitive polynomials of degree ${\displaystyle n}$ over ${\displaystyle \mathbb {F} _{q}}$. All the ${\displaystyle n}$ roots of a primitive polynomial of degree ${\displaystyle n}$ over ${\displaystyle \mathbb {F} _{q}}$ are primitive elements of ${\displaystyle \mathbb {F} _{q^{n}}}$. All primitive polynomials of degree ${\displaystyle n}$ over ${\displaystyle \mathbb {F} _{q}}$ are irreducible over ${\displaystyle \mathbb {F} _{q}}$. The number of primitive polynomials of degree ${\displaystyle n}$ over ${\displaystyle \mathbb {F} _{q}}$ is equal to ${\displaystyle \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) ${\displaystyle \mathbb {F} _{q}}$ of order ${\displaystyle n}$ has roots that are primitive elements of ${\displaystyle \mathbb {F} _{q^{n}}}$.
  • Given a primitive element ${\displaystyle \alpha \in \mathbb {F} _{q}}$, the set of powers ${\displaystyle \{1,\alpha ,\dots \alpha ^{n-1}\}}$ constitutes a polynomial basis of ${\displaystyle \mathbb {F} _{q^{n}}}$.
    • In consequence, a primitive polynomial is sometimes defined as a polynomial that generates ${\displaystyle \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

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