Primitive polynomial (field theory)

In the mathematical theory of the body a primitive polynomial is a primitive element of the minimal extension body GF (pm) over GF (p). In other words, a polynomial having the coefficients of a primitive polynomial, if it has a null in so that the amount of the whole body and also with the smallest degree of the polynomial with zero as is.

Properties

Since all minimal polynomials are irreducible and primitive polynomials are also irreducible.

A primitive polynomial must have a non-zero intercept, since it would otherwise be divisible by. Over a field of two elements is a primitive polynomial and any other primitive polynomials having an odd number of terms, since each polynomial modulo 2 is provided with an even number of terms by divisible.

An irreducible polynomial of degree over GF ( p) is a prime number is a primitive polynomial, if PM - 1 is the smallest integer for which a subgroup of.

About the field GF (pm), there is exactly primitive polynomials of degree, which is the Euler φ - function is.

The zeros of a primitive polynomial have all the order.

Applications

The analysis of structural elements

Primitive polynomials are used for the representation of elements of a finite field. If a root of a primitive polynomial, then has order, that is, all elements of can be represented as successive powers of α:

When these elements are reduced modulo, then forms the basis of all polynomial representation as said elements a body.

As the multiplicative group of a finite field is always a cyclic group is a primitive polynomial, a generator element of the multiplicative group is.

Generating pseudo - random numbers,

Primitive polynomials defining a recurrent relation can be used to generate bits of pseudo-random numbers. In fact, any linear feedback shift register is at maximum cycle ( this is 2lrsr length - 1 ) with primitive polynomials in relationship.

Be e.g. a primitive polynomial x10 x3 1 is given. You start with a custom seed number ( this may not necessarily be chosen at random ). One then takes the 10 -th, 3 -th and 0 -th bit, counting from the least significant bit, this combined with XOR and receives a new bit. The seed number is then shifted to the left and the new bit is the least significant bit of the seed number. This can be repeated to produce 210-1 = 1023 pseudo-random bits.

In general, for a primitive polynomial of degree m, that this process produces 2m-1 pseudo-random numbers before the sequence repeats itself.

Primitive trinomials

Primitive trinomials are primitive polynomials with only three non-zero terms. The trinomial are very simple and can be used for very efficient random number generators. There are various methods to determine primitive trinomial and check. A simple test works as follows: For each r, for the 2r -1 is a Mersenne prime, a trinomial of degree r is primitive if and only if it is irreducible. By recently developed by Richard P. Brent algorithms has made it possible to find primitive trinomial high degree, such as x6972593 x3037958 1 This Pseuodzufallsgeneratoren can approx 102 098 959 are generated with a huge period of 26972593-1, or.