PROFILPELAJAR.COM

In finite field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite field $GF(p m)$ . This means that a polynomial $F (X)$ of degree $m$ with coefficients in $GF(p) = Z / p Z$ is a primitive polynomial if it is monic and has a root $α$ in $GF(p m)$ such that $\{0,1,\alpha ,\alpha ^{2},\alpha ^{3},\ldots \alpha ^{p^{m}-2}\}$ is the entire field $GF(p m)$ . This implies that $α$ is a primitive ( $p m - 1$ )-root of unity in $GF(p m)$ .

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 xⁿ − 1 is n = p^m − 1.
A primitive polynomial of degree $m$ has $m$ different roots in $GF(p m)$ , which all have order $p m - 1$ , meaning that any of them generates the multiplicative group of the field.
Over GF(p) there are exactly $φ (p m - 1)$ primitive elements and $φ (p m - 1) / m$ primitive polynomials, each of degree $m$ , where $φ$ is Euler's totient function.^[1]
The algebraic conjugates of a primitive element $α$ in $GF(p m)$ are $α$ , $α p$ , $α p 2$ , …, $α p m -1$ and so the primitive polynomial $F (x)$ has explicit form $F (x) = (x - α) (x - α p) (x - α p 2) \dots (x - α p m -1)$ . That the coefficients of a polynomial of this form, for any $α$ in $GF(p n)$ , not necessarily primitive, lie in $GF(p)$ follows from the property that the polynomial is invariant under application of the Frobenius automorphism to its coefficients (using $α p n = α$ ) and from the fact that the fixed field of the Frobenius automorphism is $GF(p)$ .

Examples

Over $GF(3)$ the polynomial $x 2 + 1$ is irreducible but not primitive because it divides $x 4 - 1$ : its roots generate a cyclic group of order 4, while the multiplicative group of $GF(3 2)$ is a cyclic group of order 8. The polynomial $x 2 + 2 x + 2$ , on the other hand, is primitive. Denote one of its roots by $α$ . Then, because the natural numbers less than and relatively prime to $32 - 1 = 8$ are 1, 3, 5, and 7, the four primitive roots in $GF(3 2)$ are $α$ , $α 3 = 2 α + 1$ , $α 5 = 2 α$ , and $α 7 = α + 2$ . The primitive roots $α$ and $α 3$ are algebraically conjugate. Indeed $x 2 + 2 x + 2 = (x - α) (x - (2 α + 1))$ . The remaining primitive roots $α 5$ and $α 7 = (α 5) 3$ are also algebraically conjugate and produce the second primitive polynomial: $x 2 + x + 2 = (x - 2 α) (x - (α + 2))$ .

For degree 3, $GF(3 3)$ has $φ (3 3 - 1) = φ (26) = 12$ primitive elements. As each primitive polynomial of degree 3 has three roots, all necessarily primitive, there are $12 / 3 = 4$ primitive polynomials of degree 3. One primitive polynomial is $x 3 + 2 x + 1$ . Denoting one of its roots by $γ$ , the algebraically conjugate elements are $γ 3$ and $γ 9$ . The other primitive polynomials are associated with algebraically conjugate sets built on other primitive elements $γ r$ with $r$ relatively prime to 26:

{\begin{aligned}x^{3}+2x+1&=(x-\gamma )(x-\gamma ^{3})(x-\gamma ^{9})\\x^{3}+2x^{2}+x+1&=(x-\gamma ^{5})(x-\gamma ^{5\cdot 3})(x-\gamma ^{5\cdot 9})=(x-\gamma ^{5})(x-\gamma ^{15})(x-\gamma ^{19})\\x^{3}+x^{2}+2x+1&=(x-\gamma ^{7})(x-\gamma ^{7\cdot 3})(x-\gamma ^{7\cdot 9})=(x-\gamma ^{7})(x-\gamma ^{21})(x-\gamma ^{11})\\x^{3}+2x^{2}+1&=(x-\gamma ^{17})(x-\gamma ^{17\cdot 3})(x-\gamma ^{17\cdot 9})=(x-\gamma ^{17})(x-\gamma ^{25})(x-\gamma ^{23}).\end{aligned}}

Applications

Field element representation

Primitive polynomials can be used to represent the elements of a finite field. If α in GF(p^m) is a root of a primitive polynomial F(x), then the nonzero elements of GF(p^m) are represented as successive powers of α:

\mathrm {GF} (p^{m})=\{0,1=\alpha ^{0},\alpha ,\alpha ^{2},\ldots ,\alpha ^{p^{m}-2}\}.

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

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 2ⁿ − 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 2^m − 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 2ⁿ − 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: x^r + x^k + 1. 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.^[4]

For polynomials over GF(2), where 2^r − 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 2^r − 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 x^74207281 + x^30684570 + 1.^[5]^[6] This can be used to create a pseudo-random number generator of the huge period 2^74207281 − 1 ≈ 3×10^22338617.

References

^ Enumerations of primitive polynomials by degree over $GF(2)$ , $GF(3)$ , $GF(5)$ , $GF(7)$ , and $GF(11)$ are given by sequences A011260, A027385, A027741, A027743, and A319166 in the Online Encyclopedia of Integer Sequences.
^ C. Paar, J. Pelzl - Understanding Cryptography: A Textbook for Students and Practitioners
^ Gentle, James E. (2003). Random number generation and Monte Carlo methods (2 ed.). New York: Springer. p. 39. ISBN 0-387-00178-6. OCLC 51534945.
^ Zierler, Neal; Brillhart, John (December 1968). "On primitive trinomials (Mod 2)". Information and Control. 13 (6): 541, 548, 553. doi:10.1016/S0019-9958(68)90973-X.
^ Brent, Richard P. (4 April 2016). "Search for Primitive Trinomials (mod 2)". Retrieved 25 May 2024.
^ Brent, Richard P.; Zimmermann, Paul (24 May 2016). "Twelve new primitive binary trinomials". arXiv:1605.09213 [math.NT].