- Primitive polynomial
In field theory, a branch of
mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite extension fieldGF("p""m"). In other words, a polynomial with coefficients in GF("p") = Z/"p"Z is a primitive polynomial if it has a root in GF("p""m") such that is the entire field GF("p""m"), and moreover, is the smallest degree polynomial having as root.
ring theory, the term primitive polynomial is used for a different purpose, to mean a polynomial over a unique factorization domain(such as the integers) whose greatest common divisorof its coefficientsis a unit. This article will not be concerned with the ring theory usage.
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 φ is
Euler's totient function.
The roots of a primitive polynomial all have order "p""m" − 1.
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 α:
When these elements are reduced modulo "F"("x") they provide the
polynomial basisrepresentation of all the elements of the field.
multiplicative groupof a finite field is always a cyclic 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 registerwith maximum cycle (that is 2lfsr 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, and
xorthem 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 210−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
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 generators. 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 a Mersenne 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 26972593−1, or roughly 102098959. [http://wwwmaths.anu.edu.au/~brent/trinom.html]
* [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.