Primitive polynomial

from Wikipedia, the free encyclopedia

In the theory of mathematical fields , a primitive polynomial is the minimal polynomial of a primitive element of a field extension over finite fields . In other words, a polynomial with the coefficients from is a primitive polynomial if it has a zero in , so that the set is the whole body and also the polynomial with the smallest degree is also the zero.

properties

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

A primitive polynomial must have a non-zero constant term, otherwise it would be divisible by . Over a field of two elements is a primitive polynomial and all other primitive polynomials have an odd number of terms, since every polynomial modulo 2 with an even number of terms is divisible by .

An irreducible polynomial of degree over for a prime number is a primitive polynomial if is the smallest integer that is a divisor of .

Above the body there are exactly primitive polynomials of degree , with the Euler φ function is.

The zeros of a primitive polynomial all have the order .

Applications

Representation of body elements

Primitive polynomials are used to represent elements of a finite field . If there is a root of a primitive polynomial , then the order , i.e. all elements of can be represented as successive powers of :

If these elements are reduced modulo , then the representation as a polynomial basis of all these elements forms a field.

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

Generation of pseudo-random numbers

Primitive polynomials define a recurring relation that can be used to generate bits of pseudorandom numbers . In fact, each linear feedback shift register with maximum cycle (this is 2 lrsr length - 1) is related to primitive polynomials.

Be z. B. given a primitive polynomial . (Engl. You start with a custom seed seed , seed be, this does not necessarily chosen randomly). You then take the 10th, 3rd and 0th bit , counted from the least significant bit, combine them with XOR and get a new bit. The seed number is then shifted to the left and the new bit becomes the least significant bit of the seed number. This can be repeated to generate pseudo-random bits. Very specific outputs of the shift register are required for a maximum length sequence .

In general, for a primitive polynomial of degree , this process generates pseudo-random numbers before the sequence repeats.

Primitive trinomials

Primitive trinomials are primitive polynomials with only three non-zero terms. The trinomials are very simple and are used for very efficient random number generators. There are several methods of identifying and testing primitive trinomials. A simple test works like this: For anything that has a Mersenne prime , a trinomial of degree is primitive if and only if it is irreducible. Algorithms recently developed by Richard P. Brent have made it possible to find primitive trinomials of high degree, such as: B. . This enables pseudo-random generators with a huge period of , or approx .

literature

  • Elwyn R. Berlekamp: Algebraic Coding Theory, Revised Edition . 2nd Edition. Aegean Park Press, 1984, ISBN 0-89412-063-8 .
  • Peterson, WW, Weldon, EJ, "Error correcting codes", Cambridge, The MIT-Press, 1972
  • Anderson, GC, Finnie, BW, "Pseudo-random and random test signals", HP Journal 19, No. 1.2 1967

Web links

Individual evidence

  1. Tietze / Schenk, "Semiconductor Circuit Technology", 3rd edition 1976, pp. 590 ff, no longer described in later editions.
  2. ^ Search for Primitive Trinomials (mod 2).