In finite field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite field GF(pm).
If α in GF(pm) is a root of a primitive polynomial F(x), then the nonzero elements of GF(pm) are represented as successive powers of α: This allows an economical representation in a computer of the nonzero elements of the finite field, by representing an element by the corresponding exponent of
This representation makes multiplication easy, as it corresponds to addition of exponents modulo
Primitive polynomials over GF(2), the field with two elements, can be used for pseudorandom bit generation.
In fact, every linear-feedback shift register with maximum cycle length (which is 2n − 1, where n is the length of the linear-feedback shift register) may be built from a primitive polynomial.
[2] In general, for a primitive polynomial of degree m over GF(2), 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.
Their simplicity makes for particularly small and fast linear-feedback shift registers.
[3] A number of results give techniques for locating and testing primitiveness of trinomials.
Although the Mersenne Twister pseudo-random number generator does not use a trinomial, it does take advantage of this.