TOPICS
Search

Primitive Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A primitive polynomial of degree n over a finite field GF(q) is a monic polynomial that is irreducible and whose roots generate the multiplicative group of the extension field GF(q^n). For any prime power q and any positive integer n, there exists a primitive polynomial of degree n over GF(q). There are

a_q(n)=(phi(q^n-1))/n
(1)

primitive polynomials over GF(q), where phi(n) is the totient function.

A monic polynomial of degree n over the finite field GF(2) (i.e., with coefficients either 0 or 1) is primitive iff it has polynomial order 2^n-1. For example, x^2+x+1 has order 3 since

(x+1)/(x^2+x+1)=(x+1)/(x^2+x+1) (mod 2)
(2)
(x^2+1)/(x^2+x+1)=1+x/(x^2+x+1) (mod 2)
(3)
(x^3+1)/(x^2+x+1)=x+1 (mod 2).
(4)

Plugging in q=2 to equation (1), the numbers of primitive polynomials over GF(2) are

a_2(n)=(phi(2^n-1))/n,
(5)

giving 1, 1, 2, 2, 6, 6, 18, 16, 48, ... (OEIS A011260) for n=1, 2, .... The following table lists the primitive polynomials over the finite field GF(2) of degrees 1 through 5.

nprimitive polynomials
11+x
21+x+x^2
31+x+x^3, 1+x^2+x^3
41+x+x^4, 1+x^3+x^4
51+x^2+x^5, 1+x+x^2+x^3+x^5, 1+x^3+x^5, 1+x+x^3+x^4+x^5, 1+x^2+x^3+x^4+x^5, 1+x+x^2+x^4+x^5

Amazingly, primitive polynomials over GF(2) define a recurrence relation which can be used to obtain a new pseudorandom bit from the n preceding ones.

See also

Finite Field, Irreducible Polynomial, Polynomial, Polynomial Order, Primitive Element, Primitive Root

Explore with Wolfram|Alpha

References

Berlekamp, E. R. Algebraic Coding Theory. New York: McGraw-Hill, p. 84, 1968.Booth, T. L. "An Analytical Representation of Signals in Sequential Networks." In Proceedings of the Symposium on Mathematical Theory of Automata. New York, N.Y., April 24, 25, 26, 1962. Brooklyn, NY: Polytechnic Press of Polytechnic Inst. of Brooklyn, pp. 301-324, 1963.Church, R. "Tables of Irreducible Polynomials for the First Four Prime Moduli." Ann. Math. 36, 198-209, 1935.Fan, P. and Darnell, M. Table 5.1 in Sequence Design for Communications Applications. New York: Wiley, p. 118, 1996.O'Connor, S. E. "Computing Primitive Polynomials." http://seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/overview.html.Peterson, W. W. and Weldon, E. J. Jr. Error-Correcting Codes, 2nd ed. Cambridge, MA: MIT Press, p. 476, 1972.Ristenblatt, M. P. "Pseudo-Random Binary Coded Waveforms." In Modern Radar (Ed. R. S. Berkowitz). New York: Wiley, pp. 274-314, 1965.Ruskey, F. "Information on Primitive and Irreducible Polynomials." https://web.archive.org/web/20170516122408/http://theory.cs.uvic.ca/inf/neck/PolyInfo.html.Sloane, N. J. A. Sequence A011260/M0107 in "The On-Line Encyclopedia of Integer Sequences."Zierler, N. and Brillhart, J. "On Primitive Trinomials." Inform. Control 13, 541-544, 1968.Zierler, N. and Brillhart, J. "On Primitive Trinomials (II)." Inform. Control 14, 566-569, 1969.

Referenced on Wolfram|Alpha

Primitive Polynomial

Cite this as:

Weisstein, Eric W. "Primitive Polynomial." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PrimitivePolynomial.html

Subject classifications