- Primitive polynomial
In field theory, a branch of

mathematics , a**primitive polynomial**is the minimal polynomial of a primitive element of the finiteextension field GF("p"^{"m"}). In other words, a polynomial $F(X)$ with coefficients in GF("p") =**Z**/"p**"Z**is a primitive polynomial if it has a root $alpha$ in GF("p"^{"m"}) such that $\{0,1,\; alpha,\; alpha^2,\; alpha^3,dots,alpha^\{p^\{m\}-2\}\}$ is the entire field GF("p"^{"m"}), and moreover, $F(X)$ is the smallest degree polynomial having $alpha$ as root.In

ring theory , the term**primitive polynomial**is used for a different purpose, to mean a polynomial over aunique factorization domain (such as theinteger s) whosegreatest common divisor of itscoefficients is a unit. This article will not be concerned with the ring theory usage.**Properties**Because all minimal polynomials are irreducible, all primitive polynomials are also irreducible.

A primitive polynomial must have a non-zero constant term, for otherwise it will be divisible by "x". Over the field of two elements, all primitive polynomials have an odd number of terms, otherwise they are divisible by "x"+"1".

An irreducible polynomial of degree "m", "F"("x") over GF("p") for prime "p", is a primitive polynomial if the smallest positive integer "n" such that "F"("x") divides "x"

^{n}- 1 is "n" = "p"^{"m"}− 1.Over GF(p

^{"m"}) there are exactly φ(p^{"m"}− 1)/"m" primitive polynomials of degree "m", where φ isEuler's totient function .The roots of a primitive polynomial all have order "p"

^{"m"}− 1.**Usage****Field element representation**Primitive polynomials are used in the representation of elements of a

finite field . If α in GF("p"^{"m"}) is a root of a primitive polynomial "F"("x") then since the order of α is "p"^{"m"}− 1 that means that all elements of GF("p"^{"m"}) can be represented as successive powers of α::$GF(p^m)\; =\; \{\; 0,\; 1,\; alpha,\; alpha^2,\; ldots,\; alpha^\{p^m-2\}\; \}\; .$

When these elements are reduced modulo "F"("x") they provide the

polynomial basis representation of all the elements of the field.Since the

multiplicative group of a finite field is always acyclic group , a primitive polynomials "f" is a polynomial such that "x" is a generator of the multiplicative group in GF(p) [x] /f(x)**Pseudo-Random bit generation**Primitive polynomials define a recurrence relation that can be used to generate pseudorandom bits. In fact every

linear feedback shift register with maximum cycle (that is 2^{lfsr length}- 1) is related with primitive polynomial.For example, given the primitive polynomial "x"

^{10}+ "x"^{3}+ 1, we start with a user-specified bit seed (it need not randomly be chosen, but it can be). We then take the 10th, 3rd, and 0th bits of it, starting from the least significant bit, andxor them together, obtaining a new bit. The seed is then shifted left and the new bit is made the least significant bit of the seed. This process can be repeated to generate 2^{10}−1 = 1023 pseudo-random bits.In general, for a primitive polynomial of degree "m", this process will generate 2

^{"m"}−1 pseudo-random bits before repeating the same sequence**Primitive trinomials**The most useful kind of primitive polynomials are primitive trinomials, those having only three nonzero terms, because they are the simplest and result in the most efficient

pseudo-random number generator s. A number of results give techniques for locating and testing primitiveness of trinomials. One simple test is the following: for every "r" such that 2^{"r"}−1 is aMersenne prime , a trinomial of degree "r" is primitive if and only if it is irreducible. Recent algorithms invented by Richard Brent have enabled the discovery of primitive trinomials of very large degree, such as "x"^{6972593}+ "x"^{3037958}+ 1. This can be used to create a pseudo-random number generator of the huge period 2^{6972593}−1, or roughly 10^{2098959}. [*http://wwwmaths.anu.edu.au/~brent/trinom.html*]**External links*** [

*http://mathworld.wolfram.com/PrimitivePolynomial.html MathWorld entry on primitive polynomial*]

* [*http://planetmath.org/encyclopedia/PrimitivePolynomial.html PlanetMath entry on primitive polynomial*]

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**primitive polynomial**— Math. a polynomial that has content equal to 1. Cf. content1 (def. 10). * * * … Universalium**primitive polynomial**— Math. a polynomial that has content equal to 1. Cf. content1 (def. 10) … Useful english dictionary**Primitive**— is a subjective label used to imply that one thing is less sophisticated or less advanced than some other thing. Being a comparative word it is also relative in nature.Indigenous peoples and their beliefs and practices are sometimes described as… … Wikipedia**Polynomial factorization**— In mathematics and computer algebra, polynomial factorization typically refers to factoring a polynomial into irreducible polynomials over a given field. Formulation of the questionOther factorizations, such as square free factorization exist,… … Wikipedia**Primitive element (finite field)**— In field theory, a branch of mathematics, a primitive element of a finite field GF ( q ) is a generator of the multiplicative group of the field, which is necessarily cyclic. The minimal polynomial of a primitive element is a primitive polynomial … Wikipedia**Polynomial basis**— In mathematics, the polynomial basis is a basis for finite extensions of finite fields.Let α ∈ GF( p m ) be the root of a primitive polynomial of degree m over GF( p ). The polynomial basis of GF( p m ) is then:{ 0, 1, alpha, ldots, alpha^{m… … Wikipedia**Polynomial**— In mathematics, a polynomial (from Greek poly, many and medieval Latin binomium, binomial [1] [2] [3], the word has been introduced, in Latin, by Franciscus Vieta[4]) is an expression of finite length constructed from variables (also known as… … Wikipedia**Primitive ring**— In mathematics, especially in the area of abstract algebra known as ring theory, the concept of left primitive ring generalizes that of matrix algebra. Every matrix ring is the endomorphism ring of a finite dimensional vector space, but a… … Wikipedia**Primitive element theorem**— In mathematics, more specifically in field theory, the primitive element theorem provides a characterization of the finite field extensions which are simple and thus can be generated by the adjunction of a single primitive element. Primitive… … Wikipedia**Polynomial ring**— In mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the set of polynomials in one or more variables with coefficients in another ring. Polynomial rings have influenced much of mathematics, from the … Wikipedia