Primitive polynomial (field theory)
|This article needs additional citations for verification. (May 2010)|
In field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite extension field GF(pm). In other words, a polynomial with coefficients in GF(p) = Z/pZ is a primitive polynomial if its degree is m and it has a root in GF(pm) such that is the entire field GF(pm). This means also that is a primitive (pm-1)-root of unity in GF(pm).
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, x+1 is a primitive polynomial and all other primitive polynomials have an odd number of terms, since any polynomial mod 2 with an even number of terms is divisible by x+1 (it has 1 as a root).
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 xn - 1 is n = pm − 1.
Over GF(pm) there are exactly φ(pm − 1)/m primitive polynomials of degree m, where φ is Euler's totient function.
A primitive polynomial of degree m has m different roots in GF(pm), which all have order pm − 1. This means that, if is such a root, then and for 0 < i < pm - 1.
Field element representation
Primitive polynomials are used in the representation of elements of a finite field. If α in GF(pm) is a root of a primitive polynomial F(x) then since the order of α is pm − 1 that means that all elements of GF(pm) can be represented as successive powers of α:
When these elements are reduced modulo F(x) they provide the polynomial basis representation of all the elements of the field.
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 2lfsr length − 1) is related with primitive polynomial.
For example, given the primitive polynomial x10 + x3 + 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 xor 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 210 − 1 = 1023 pseudo-random bits.
In general, for a primitive polynomial of degree m, this process will generate 2m − 1 pseudo-random bits before repeating the same sequence
The cyclic redundancy check (CRC) is an error-detection code that operates by interpreting the message bitstring as the coefficients of a polynomial over GF(2) and dividing it by a fixed generator polynomial also over GF(2); see Mathematics of CRC. Primitive polynomials, or multiples of them, are a good choice for generator polynomials because they can reliably detect two bit errors that occur far apart in the message bitstring, up to a distance of 2n − 1 for a degree n primitive polynomial.
A useful class of primitive polynomials is the 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.
For trinomials over GF(2), there is a simple test: for every r such that 2r − 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 over GF(2) of very large degree, such as x6972593 + x3037958 + 1. This can be used to create a pseudo-random number generator of the huge period 26972593 − 1, or roughly 102098959.