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 GF, 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 . An irreducible polynomialF of degree m over GF, where p is prime, is a primitive polynomial if the smallest positive integern such that F divides is. Over GF there are exactly primitive polynomials of degree m, where φ is Euler's totient function. A primitive polynomial of degree m has m different roots in GF, which all have order. This means that, if α is such a root, then and for. The primitive polynomial F of degree m of a primitive elementα in GF has explicit form.
Usage
Field element representation
Primitive polynomials are used in the representation of elements of a finite field. If α in GF is a root of a primitive polynomial F then since the order of α is that means that all nonzero elements of GF can be represented as successive powers of α: When these elements are reduced modulo F, they provide the polynomial basis representation of all the elements of the field. Since the multiplicative group of a finite field is always a cyclic group, a primitive polynomial f is a polynomial such that x is a generator of the multiplicative group in GF/f
Pseudo-random bit generation
Primitive polynomials over GF, the field with two elements, can be used for pseudorandom bit generation. In fact, every linear feedback shift register with maximum cycle length may be built from a primitive polynomial. For example, given the primitive polynomial, we start with a user-specified nonzero 10-bit seed occupying bit positions 1 through 10, starting from the least significant bit.. We then take the 10th and 3rd bits, and create a new 0th bit, so that the xor of the three bits is 0. The seed is then shifted left one position so that the 0th bit moves to position 1. This process can be repeated to generate pseudo-random bits. In general, for a primitive polynomial of degree m over GF, this process will generate pseudo-random bits before repeating the same sequence.
CRC codes
The cyclic redundancy check is an error-detection code that operates by interpreting the message bitstring as the coefficients of a polynomial over GF and dividing it by a fixed generator polynomial also over GF; see Mathematics of CRC. Primitive polynomials, or multiples of them, are sometimes 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 for a degree n primitive polynomial.
Primitive trinomials
A useful class of primitive polynomials is the primitive trinomials, those having only three nonzero terms:. Their simplicity makes for particularly small and fast linear feedback shift registers. A number of results give techniques for locating and testing primitiveness of trinomials. For polynomials over GF, where is a Mersenne prime, a polynomial of degree r is primitive if and only if it is irreducible. Although the Mersenne Twisterpseudo-random number generator does not use a trinomial, it does take advantage of this. Richard Brent has been tabulating primitive trinomials of this form, such as. This can be used to create a pseudo-random number generator of the huge period ≈.
