Primitive polynomial (field theory)

Short description: Minimal polynomial of a primitive element in a finite field

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 is monic and has a root α in GF(pm) such that [math]\displaystyle{ \\{0,1,\alpha, \alpha^2,\alpha^3, \ldots \alpha^{p^m-1}\\} }[/math] is the entire field GF(pm). This implies that α is a primitive (pm − 1)-root of unity in GF(pm).

## Contents

* 1 Properties
* 2 Usage
* 2.1 Field element representation
* 2.2 Pseudo-random bit generation
* 2.3 CRC codes
* 3 Primitive trinomials
* 4 References
* 5 External links

## Properties

* 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(p) 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

### Field element representation

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 α:

[math]\displaystyle{ \mathrm{GF}(p^m) = \\{ 0, 1= \alpha^0, \alpha, \alpha^2, \ldots, \alpha^{p^m-2} \\} . }[/math]

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 [math]\displaystyle{ \alpha. }[/math] This representation makes multiplication easy, as it corresponds to addition of exponents modulo [math]\displaystyle{ p^m-1. }[/math]

### Pseudo-random bit generation

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]

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

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

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.[2] A number of results give techniques for locating and testing primitiveness of trinomials.[3]

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.[4][5] This can be used to create a pseudo-random number generator of the huge period 274207281 − 1 ≈ 3×1022338617.

## References

1. ↑ C. Paar, J. Pelzl - Understanding Cryptography: A Textbook for Students and Practitioners
2. ↑ Gentle, James E. (2003). Random number generation and Monte Carlo methods (2 ed.). New York: Springer. pp. 39. ISBN 0-387-00178-6. OCLC 51534945. https://www.worldcat.org/oclc/51534945.
3. ↑ Zierler, Neal; Brillhart, John (December 1968). "On primitive trinomials (Mod 2)" (in en). Information and Control 13 (6): 541,548,553. doi:10.1016/S0019-9958(68)90973-X.
4. ↑ Brent, Richard P. (4 April 2016). "Search for Primitive Trinomials (mod 2)". http://maths.anu.edu.au/~brent/trinom.html.
5. ↑ Brent, Richard P.; Zimmermann, Paul (24 May 2016). "Twelve new primitive binary trinomials". arXiv:1605.09213 [math.NT].

## External links

* Weisstein, Eric W.. "Primitive Polynomial". http://mathworld.wolfram.com/PrimitivePolynomial.html.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Primitive polynomial (field theory). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Primitive_polynomial_(field_theory)&oldid=2640926"