Primitive polynomial (field theory)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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). This means that a polynomial F(X) of degree m with coefficients in GF(p) = Z/pZ is a primitive polynomial if it has a root α in GF(pm) such that {0, 1, α, α2, α3, ..., αpm−2} is the entire field GF(pm). This implies that α is a primitive (pm − 1)-root of unity in GF(pm).

Properties[edit]

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(2), 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 F(x) of degree m over GF(p), where p is prime, 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 αpm−1 = 1 and αi ≠ 1 for 0 < i < pm − 1.

The primitive polynomial F(x) of degree m of a primitive element α in GF(pm) has explicit form F(x) = (xα)(xαp)(xαp2)⋅⋅⋅(xαpm−1).

Usage[edit]

Field element representation[edit]

Primitive polynomials can be used to represent the elements of a finite field. 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

Pseudo-random bit generation[edit]

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.[1]

For example, given the primitive polynomial p(x) = x10 + x3 + 1, we start with a user-specified nonzero 10-bit seed occupying bit positions 1 through 10, which represent the coefficients of a polynomial over GF(2), starting from the least significant bit. (The seed need not randomly be chosen, but it can be). The seed is then shifted left one position so that the 0th bit moves to position 1, which accomplishes multiplying by x, the primitive element of GF(2^10)[x]/p(x) . We then take the 10th and 3rd bits, and create a new 0th bit, so that the xor of the three bits is 0, which accomplishes division modulo p(x). This process can be repeated to generate 210 − 1 = 1023 pseudo-random bits.

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.

CRC codes[edit]

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 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 2n − 1 for a degree n primitive polynomial.

Primitive trinomials[edit]

A useful class of primitive polynomials is the primitive trinomials, those having only three nonzero terms: xr + xk + 1. 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(2), where 2r − 1 is a Mersenne prime, a polynomial of degree r is primitive if and only if it is irreducible. (Given an irreducible polynomial, it is not primitive only if the period of x is a non-trivial factor of 2r − 1. Primes have no non-trivial factors.) Although the Mersenne Twister pseudo-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 x74207281 + x30684570 + 1.[2][3] This can be used to create a pseudo-random number generator of the huge period 274207281 − 13×1022338617.

References[edit]

  1. ^ C. Paar, J. Pelzl - Understanding Cryptography: A Textbook for Students and Practitioners
  2. ^ Brent, Richard P. (4 April 2016). "Search for Primitive Trinomials (mod 2)". Retrieved 4 June 2020.
  3. ^ Brent, Richard P.; Zimmermann, Paul (24 May 2016). "Twelve new primitive binary trinomials". arXiv:1605.09213 [math.NT].

External links[edit]