# COMPUTING PRIMITIVE POLYNOMIALS - THEORY AND ALGORITHM

## Sean E. O'Connor

Copyright © 1986-2022 by Sean Erik O'Connor. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled GNU Free Documentation License

### Introduction

This technical note explains in great detail the technique used to compute primitive polynomials from the paper by Alanen and Knuth with extensions due to Sugimoto . Prerequisites: Knowledge of elementary number theory, and finite fields as covered in books on abstract algebra. See the references.

I have a C++ program which computes primitive polynomials of arbitrary degree n modulo any prime p.

### Fast Review of Number Theory, Finite Fields and Combinatorics

Here is an ultra-fast review of some basic results we'll need to use.

#### Number Theory

##### Primitive Roots

An integer $a$ is defined to be a primitive root of the prime $p$ if $a^k \ne 1 (mod \: p)$ for $0 \lt k \lt p-1$ but $a^{p-1} \equiv 1 (mod \: p)$ i.e. the integer a generates the cyclic group $\{ 1, 2, 3, ..., p-1 \}$ under modulo $p$ multiplication. Primitive roots exist for all prime p. Example: 2 is a primitive root of 3 because $2^1 \equiv 2 \not \equiv 1 (mod \: 3)$ but $2^2 \equiv 1 (mod \: p)$

##### Euler Phi Function

The Phi or Totient function is defined by $\phi( 1 ) = 1$ and $\phi( n )$ = (number of integers between 1 and n-1 relatively prime to n) for $n \gt 1$

Integers a and b are defined to be relatively prime (coprime) if the greatest common divisor of a and b is 1). For prime p, $$\phi( p ) = p-1$$ In general, if n has the prime factorization $$n = p_1^{e_1} \ldots p_k^{e_k}$$ then $$\phi( n ) = n \left( 1 - {1 \over {p_1}} \right) \ldots \left( 1 - {1 \over {p_k}} \right)$$

Example: $\phi( 18 ) = \phi( 2 \bullet 3^2 ) = 18 \bullet ( 1 - {1 \over 2} )( 1 - {1 \over 3} ) = 6$ = number of integers between 1 and 17 relatively prime to 18 = # {1, 5, 7, 11, 13, 17}

We have the following bounds for $\phi$, for $n \ge 3$ $${n \over { e^\gamma \log \log n + {5 \over {2 \log \log n}} } } \lt \phi(n) \le n$$ except when $n = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 = 223092870$ where $\gamma$ is Euler's constant, in which case $${n \over { e^\gamma \log \log n + {2.50637 \over {2 \log \log n}} } } \lt \phi(n) \le n$$ For our example, this is 4.239 < φ ( 18 ) ≤ 18. A looser lower bound is $\phi(n) \ge \sqrt{ n } \text{ for } n \ge 6$. Euler's Totient with upper and lower bounds.
##### Fermat's Little Theorem

If p is a prime and p does not divide a, then $a^{p-1} \equiv 1 (mod \: p)$ and for any integer a, $a^p \equiv a (mod \: p)$. For example, $3^7 \equiv 3 \bullet 9^3 \equiv 3 \bullet 2^3 \equiv 3 (mod \: 7)$

#### Finite Fields

##### Basic Properties

Any finite field has $p^n$ elements where n is 1 or greater and p is prime. All fields with the same number of elements are isomorphic. A field with $p^n$ elements is called Galois Field $GF \left( p^n \right)$.

##### Polynomial Representation

The Galois field $GF \left( p^n \right)$ is a quotient ring $GF ( p ) [ x ] / ( g(x) )$ where g(x) is any monic irreducible polynomial of degree n with coefficients in GF(p), and (g(x)) is the maximal principle ideal generated by g(x). In other words, it is an algebraic extension of GF(p).

The field is exactly the set of all polynomials of degree 0 to n-1 with the two field operations being addition and multiplication of polynomials modulo g(x) and with modulo p integer arithmetic on the polynomial coefficients.

For example, the field $GF( 3^2 ) = GF( 3 ) / (x^2 + x + 2)$ is the set of polynomials $\{ 0, 1, 2, x, x+1, x+2, 2x, 2x+1, 2x+2 \}$ with addition and multiplication of polynomials modulo $x^2 + x + 2$ and modulo 3.

##### Exponential Representation

$GF \left( p^n \right)$ forms a cyclic group of order $p^n-1$ under multiplication with the elements, $\{ 1, a, a^2, \ldots, a^{p^n-2} \}$ where the field element $a$ is called a generator of the group (or primitive element of the field). Multiplication is defined by $a^i \bullet a^j = a^{(i+j) mod( p^n - 1 )}$ For consistency, we define the zero element of the field as $a^{-\infty} = 0$. Zero is not a primitive element.

Example: We show that $a = 2x$ is a primitive element of the field $GF( 3^2 )$ by multiplying out powers of a.

$$a = 2x$$

$$a^2 = 4 x^2 (mod \: x^2 + x + 2, mod \: 3) = 2x + 1$$

$$a^3 = x + 1$$

$$a^4 = 2$$

$$a^5 = x$$

$$a^6 = x + 2$$

$$a^7 = 2 x + 2$$

$$a^8 = a^{8 \: mod( 3^2 - 1 )} = a^0 = 1$$

##### Primitive Elements of a Field

The field element $a^s$ is a primitive element iff $gcd( s, p^n-1 ) = 1$

Thus, it's intuitively obvious there are $\phi( p^n - 1 )$ primitive elements. In the example above, $GF(3^2)$ has $\phi(8) = 4$ primitive elements, and they are $\{ a, a^3, a^5, a^7 \} = \{2x, x+1, x, 2x + 2 \}$

##### Fermat's Theorem for a Field

Any field element a satisfies the equation $a^{p^n} \equiv a$ and non-zero field elements satisfy $a^{p^n-1} \equiv 1$. Example: $a^8 = 1$ in $GF( 3^2 )$.

##### Polynomial Identity

Any polynomial $f(x)$ with coefficients in $GF( p )$ obeys the identity $f( x^p ) ={[ f( x ) ]}^p$. This implies, if $B$ is any root of $f(x)$ in $GF \left( p^n \right)$ then then so are $\{ B, B^p, B^{p^2}, B^{p^3}, \ldots \}$ Example: if $f(x) = x^2 + x + 2$ then $f( x^3 ) = (x^3)^2 + (x^3) + 2 = (x^2 + x + 2)^3 = {f( x )^3} (mod \: 3)$

##### Prime Subfield

$GF( p )$ is the smallest subfield of $GF( p^n )$. It is the field of integers under modulo $p$ arithmetic. An element $a \in GF( p^n )$ is isomorphic to an element of $GF( p )$ if it satisfies the equation, $a^p \equiv a$ For example, for $a^4 = 2$ above, $(a^4)^3 \equiv a^{12 \: mod \: 8} \equiv a^4$

##### Minimal Polynomial

The minimal polynomial $f( x )$ of a field element $B \in GF( p^n )$ is the unique polynomial of lowest degree which has $B$ as a root and whose coefficients lie in $GF( p )$. More precisely, the coefficients are allowed to be in $GF( p^n )$ as long as they are isomorphic to elements of $GF( p )$ Example: $h( z ) = z^2 + 2z + 2 = (z - a) (z - a^3)$ is the minimal polynomial of $a = 2x$

##### Conjugates

The conjugates of a field element $B \in GF( p^n )$ are the r elements, $\{ B, B^p, B^{p^2}, B^{p^3}, \ldots , B^{p^{r - 1}} \}$ where $r \le n$ is the smallest integer for which $B^{p^r} \equiv B$ Example: $B$ has $r = 2$ conjugates, $B = a = 2x$ and $B^3 = a^3 = x + 1$ because $B^{3^2} \equiv a^9 \equiv B$

##### Minimal Polynomial Formula

The conjugates of the field element $B$ are exactly the roots of the minimal polynomial for $B$. The minimal polynomial can then be written explicitly as $$f(x)=(x-B)(x-B^p)(x-B^{p^2}) \ldots (x-B^{p^{r-1}})$$ Example: The minimal polynomial $h(z) = z^2 + 2z + 2 = a^0z^2 + a^4z + a^4$ factors as $h(z)=(z-a)(z-a^3)=(z-2x)(z-(x+1))$

#### Group Theory: Generators of a Cyclic Group

In the cyclic group $G = (a) = \{1, a, a^2, \ldots, a^{N-1}\}$ of order $N$, the element $a^s$ is a generator if and only if s and N are relatively prime. That is why $\{ a^1, a^3, a^5, a^7 \}$ were primitive elements of the field $GF( 3^2 )$. There are $\phi( N )$ generators.

#### Combinatorics: Principle of Inclusion and Exclusion

Suppose we are given a set S and m of its subsets, $\{S_1, S_2, \ldots, S_m\}$. Let $\lVert S \lVert$ denote the number of elements in a set S. Then we have the formula, $$\lVert S - \bigcup_{i=1}^m S_i = \lVert S \lVert - \sum_{1 \le i \le m} \lVert S_i \lVert +$$ $$\sum_{1 \le i \lt j \le m} \lVert S_i \cap S_j \lVert - \sum_{1 \le i \lt j \lt k \le m} \lVert S_i \cap S_j \cap S_k \lVert$$ $$+ \ldots {(-1)}^m \lVert S_1 \cap \ldots S_m \lVert.$$ Example: Use inclusion and exclusion to count the number of primes between 1 and 10 by subtracting off all multiples of 2, 3, 4, ..., 10. (1 is counted along with the primes). Let $S = {1,2,3, \ldots, 10}$, m = 9, and let $S_i$ be the set of multiples of i+1 except itself. Then $$\lVert S \lVert = 10, \lVert S_1 \lVert = \lVert {4,6,8,10} \lVert = 4,$$ $$\lVert S_2 \lVert = \lVert {6,9} \lVert = 2 \lVert S_3 \lVert = \lVert {8} \lVert = 1,$$ $$\lVert S_4 \lVert = \lVert {10} \lVert = 1$$ $$S_5 \text{ through } S_9 \text{ are empty }$$ $$\lVert S_1 \cap S_2 \lVert = \lVert \{ 4, 6, 8, 10 \} \cap \{ 6, 9 \} \lVert = \lVert {6} \lVert = 1$$ and $$\lVert S_1 \cap S_3 \lVert = \lVert = \lVert S_1 \cap S_4 \lVert = 1$$ All other intersections are empty as are all intersections of 3 or more sets. The inclusion and exclusion principle then gives us $$\lVert S - \bigcup_{i=1}^m S_i =$$ $$10 - (4 + 2 + 1 + 1) - (1 + 1 + 1) - 0 + \ldots + 0 = 5$$ which agrees with the direct calculation, $$\lVert S - \bigcup_{i=1}^m S_i = \lVert \{ 1, 2, 3, \ldots, 10 \} -$$ $$\{ 4, 6, 8, 10 \} \lVert = \lVert \{ 1, 2, 3, 5, 7 \} \lVert = 5.$$

### Definition of Primitive Polynomial

f(x) is a primitive polynomial iff the field element x generates the cyclic group of non-zero field elements of the finite field $GF( p^n )$ where p is prime and $n \ge 2$. In particular, as a generator of the non-zero field elements, f(x) satisfies the equations

$$x^{p^n-1} \equiv 1 (mod f(x), p)$$ but $$x^m \not\equiv 1 (mod f(x), p) \text{ for } 1 \le m \le p^n-2$$

The probability that a random f(x) is a primitive polyomial is $P(n,p)={{\phi(p^n-1)/n} \over {p^n-1}}$ which is bounded above and below by $${1 \over n} \left( {1 \over {e^\gamma (\log n + \log \log p) + {5 \over {2 \log n + \log \log p}}}} \right) \lt P(n,p) \le {1 \over n}$$ for $n \ge 3$ and $n \ne 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 = 223092870$ where $\gamma$ is Euler's constant.

The factor in parentheses falls slowly to approximately 0.0623901 for n = p = 1000, so if we generate polynomials at random and are able to test them quickly for primitivity, we have a fast algorithm.

### Algorithm for Finding Primitive Polynomials

Instead of checking pn-1 conditions for each candidate polynomial, as in the definition, we can reduce the number of conditions to the number of distinct prime factors of $(p^n - 1)/(p-1)$. For example, for a primitive polynomial of degree 9 modulo 3, we test 2 conditions instead of 19,682: $(3^9 - 1)/(3-1) = 13 * 757$ and for degree 10 modulo 2, we can test 3 conditions instead of 1023.

Step 0) Factor $r = {{p^n-1} \over {p-1}}$ into distinct primes: $r = p_1^{e_1} \ldots p_k^{e_k}$ Note that when $r = {{2^n-1} \over {2-1}}$ is a Mersenne prime we can skip all time-consuming factoring, and search for very high degree primitive polynomials.

Step 1) Generate a new nth degree monic polynomial (randomly or sequentially) of the form, $f(x) = x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0$ where we take care that all $p^n$ possible combinations of coefficients are generated exactly once.

Step 2) Check that $( -1 )^n a_0$ is a primitive root of the prime p. Use the quick test that a is a primitive root of prime p iff $a^{ {{p-1} \over q} } \ne 1 (mod \: p)$ for all prime $q \vert (p-1)$ Of course, $a \ne 0 (mod \: p)$ and 1 is the primitive root of $p=2$. Empirically, about 37% of random integers in $[ 0, p-1 ]$ are primitive roots of p.

Step 3) Check for absence of linear factors by testing that $f(a) \ne 0 (mod \: p)$ for $1 \le a \le p-1$ When $n \ge p$ 63.2% of polynomials will have linear factors and be rejected.

Step 4) Check if f( x ) has two or more irreducible factors using the Berlekamp polynomial factorization method, and reject it as not primitive if it does. The probability that a random polynomial of degree n is irreducible is between $1 \over 2n$ and $1 \over n$.

Step 5) Check if $x^r \equiv a \: (mod \: f(x), p)$ for some integer $a$. Most polynomials are rejected here.

Step 6) Check $a \equiv (-1)^n a_0 (mod \: p)$

Step 7) Check $x^m \ne \text{integer} \: (mod \: f(x), p)$ for $m \in \{ {r \over {p_1}}, {r \over {p_2}}, \ldots {r \over {p_k}} \}$ But skip the test for $m = {r \over p_i} \: \text{if} \: p_i \vert (p-1)$

Step 8) If the polynomial f(x) passes tests in steps 1-7, stop. It is a primitive polynomial of degree n, modulo p. Otherwise, repeat steps 1-7 until a primitive polynomial is found in not more than pn iterations.

Factoring r into primes is the time consuming part, followed by computing $x^n \: (mod \: f(x), p)$ on the coefficients, but is still much faster than attemping to use the definition of primitive polynomial directly.

### Primitive Polynomial Testing in SageMath

Let's illustrate the steps involved in the algorithm using SageMath. This Jupyter SageMath notebook is distributed under the terms of the GNU General Public License.             ### Theory Behind the Algorithm

#### More Properties of Primitive Polynomials

We'll show primitive polynomials are exactly the minimal polynomials of the primitive elements of a field.

Theorem. Any minimal polynomial of a primitive element $a \in GF(p^n)$ with $p \ge 2$ prime and $n \gt 1$ is a primitive polynomial.

Proof. Let $f(x)$ be the minimal polynomial of the primitive field element $a$. Recall a field always contains a primitive element and minimal polynomials exist for each field element. We'll show $x$ is a generator of the field.

Suppose to the contrary, that $x^m \equiv 1 \: (mod \: f(x), p)$ for some $m$, $1 \le m \le p^n-2$. Then there is an $h(x)$ such that $x^m - 1 \equiv h(x) f(x) (mod \: p)$ Since $f$ is a minimal polynomial of $a$, it has $a$ as a root: $f(a) \equiv 0 \: (mod \: f(x), p)$ so $a^m \equiv 1 \: (mod f(x), p)$ contradicting the primitivity of a because its order is not maximal.

By Fermat's theorem for fields, the non-zero field element x satisfies $x^{p^n-1} \equiv 1 \: (mod f(x), p)$ so $x$ is a generator of the field, and $f(x)$ is a primitive polynomial. $\blacksquare$

Theorem. The minimal polynomial f(x) of the primitive element a has the explicit formula, $$f( x ) = (x - a)(x - a^p)(x - a^{p^2}) \dots (x - (a^s)^{p^{n - 1}})$$ where the roots of f(x) are the n conjugates of a.

Proof. By the minimal polynomial formula, $$f( x ) = (x - a)(x - a^p)(x - a^{p^2}) \dots (x - (a^{p^{r - 1}})$$ where r is the least integer such that $$a^{p^r} = a$$

But a is a primitive element, so all the powers of a are distinct, until by Fermat's theorem for fields, $$a^{p^n} = a$$ Thus r=n. $\blacksquare$

Theorem. Any primitive polynomial f(x) of degree n modulo p is the minimal polynomial of a primitive element of the field.

Proof. Suppose f(x) is a primitive polynomial of degree n modulo p. Then x is a primitive element of the field $GF( p^ n )$ i.e. it generates the field. x is a root because $f( x ) \equiv 0 (mod f( x ), p )$ By the polynomial field identity, the powers of x, $\{ x, x^p, x^{p^2}, \ldots , x^{p^{n-1}} \}$ are also roots. They are all distinct since x is a generator and has maximal order. Since the degree of f is n, there can be no more roots. Thus f(x) is the minimal polynomial of the primitive element x. $\blacksquare$

Theorem. A primitive polynomial f(x) is irreducible in GF(p). (As an aside, polynomials which are irreducible, but not primitive also generate fields, but they are minimal polynomials of non-primitive elements.)

Proof. If not, we'd have f(x)=g(x) h(x) for some polynomials of degree < n. But then g(x) h(x) = 0 \: (mod \: f(x), p), and our field would have zero divisors, a contradiction. $\blacksquare$

Theorem. For any primitive polynomial f(x), $f( a ) \not\equiv 0 \quad \text{for } a \in \{ 0, 1, \ldots , p-1 \}$ If f(x) has zeros in GF(p), it would contains linear factors, contradicting irreducibility. $\blacksquare$

#### Algorithm For Finding Primitive Polynomials

We develop an efficient test for a polynomial to be primitive. It is like "factoring" the original definition into two simpler ones.

Lemma. Suppose n is the smallest integer for which $x^n \equiv 1 \: (mod \: f( x ), p )$ if $x^m \equiv 1 \: (mod \: f( x ), p )$ then $n | m$

The same result holds if we replace the condition $\equiv 1$ with the condition $\equiv \text{ integer }$.

Also, for any integer a and prime p, if n is the smallest number for which $a^n \equiv 1 (mod \: p)$ and $a^m \equiv 1 (mod \: p)$ then $n | m$

Proof. Since n is the smallest such number, $m > n$ so by the division algorithm, $m = n q + r \text{ where } 0 \le r \lt n$ which gives $$1 \equiv x^m \equiv x^{n q + r} \equiv {\left( x^n \right)}^q x^r \: (mod \: f( x ), p)$$ $$\equiv 1^q x^r (mod \: f( x ), p )$$

But since r < n, this would contradict the minimality of n unless r=0. Thus $m = n q$ or $n | m$ The same exact reasoning based on minimal order holds for the other two conditions. $\blacksquare$

Theorem. Let r be the smallest number for which $x^r \equiv a \: (mod \: f( x ), p)$ for some integer a and let k be the smallest number for which $x^k \equiv 1 \: (mod \: f( x ), p)$ (Such numbers always exists by Fermat's theorem for fields and the well-ordering principle.)

Given a, let t be the smallest number for which $a^t \equiv 1 (mod \: p)$ then $k = r t$

Proof. Observe $x^{rt} \equiv { \left( x^r \right) }^t \equiv 1 \: (mod \: f( x ), p )$ By the lemma, $k | r t$ But since 1 is an integer, by the lemma, we must have $r | k$ From these divisibility results, we can write for some integers u and v, $r t = k u$ and $k = v r$ giving $r t = v r u$ and by cancellation, $t = u v$ But then $${\large 1 \equiv x^k \equiv x^{ {r t} \over u} \equiv { \left( x^r \right) }^{t \over u} \equiv }$$ $${\large a^{t \over u} \: (mod \: f( x ), p ) \equiv a^{ {u v} \over u} \equiv a^v (mod \: p) }$$ By the lemma, $t | v$ But we already had $v | t$ from $t = u v$, so $t = v$, implying $u = 1$ implying $k = r t$ $\blacksquare$

Corollary. Given the definition of the numbers r and t as in the lemma above, if $r = {{p^n - 1} \over {p - 1}}$ and $t = p - 1$ then $k = p^n - 1$ so $f( x )$ is a primitive polynomial by definition.

Theorem. Let's go in the opposite direction. Defining r, t and k as in the lemma, let f(x) be primitive. It follows that $r = {{p^n - 1} \over {p - 1}}$ and $t = p - 1$

Proof. Since $f(x)$ is primitive, $k = p^n - 1$ Now our first theorem says $k = rt$ Next, by Fermat's theorem, $a^{p-1} \equiv 1 (mod \: p)$ so by the lemma, $t \vert (p-1)$ and then for some s, $p-1 = st$ Combining all of this, $$rt = k = p^n-1 = (p-1) {p^n-1 \over p-1} = st {p^n-1 \over p-1}$$ Upon cancelling t, $r = s {p^n-1 \over p-1}$ or ${p^n-1 \over p-1} \vert \: r$ Now we show $r \: \vert \: {p^n-1 \over p-1}$ which will force the equality $r ={p^n-1 \over p-1}$ and prove the first part of the theorem.

A field element, $GF( p^n )$ is an element of $GF(p)$ iff its p-1 power is 1. $${\left( x^{ {p^n - 1} \over {p-1} } \right)}^{p-1} \equiv x^{p^n - 1} \equiv 1 \: (mod \: f(x), p)$$ by the primitivity of $f(x)$, proving $$x^{ {p^n - 1} \over {p-1} } \equiv \text{integer} \: (mod \: f(x), p)$$ By the lemma, $r \: \vert \: {p^n-1 \over p-1}$ The value of t is $t = {k \over r} = (p^n - 1) / ({{p^n - 1} \over {p - 1}}) = p - 1$ $\blacksquare$

Let's summarize all of this in a theorem:

Theorem. f(x) is a primitive polynomial iff these two conditions hold: The smallest value of r such that $x^r \equiv a \: (mod \: f(x), p)$ for some integer a is $r = { p^n - 1 \over p - 1}$ The smallest value of t such that $a^t \equiv 1 (mod \: p)$ is $t = p - 1$ In other words $a$ must be a primitive root of $p$.

#### The Polynomial's Constant Term

Theorem. Let f(x) be a primitive polynomial of degree n, modulo p. The constant term of f is $a_0 = {(-1)}^n x^r \: (mod \: f(x), \: p)$

Proof. By the lemma, the primitive polynomial can be written as $f(z) = z^n + a_{n-1} z^{n-1} + \ldots + a_1 z + a_0$ and as the minimal polynomial $f(z) = (z-x){(z - x^p)} \ldots (z - x^{p^{n-1}})$ Multiplying out and comparing constant terms gives $a_0 = (-x) {(-x)}^p \ldots (-x^{p^{n-1}}) = {(-1)}^n x^{1 + p + \ldots + p^{n-1}}$ which by geometric progression is $a_0 = {(-1)}^n x^{{p^n -1} \over {p-1}} \: (mod \: f(x), \: p)$ $\blacksquare$

Corollary. ${(-1)}^n a_0 = a (mod \: p)$ where $a$ is the integer of the theorem earlier. Also, $a$ is a primitive root of $p$.

Proof. $a_0 = {(-1)}^n x^r (mod \: f(x), \: p) \equiv {(-1)}^n a (mod \: p)$ Thus ${(-1)}^n a_0 \equiv a(mod \: p)$ But $a$ is a primitive root of $p$ by the theorem, so ${(-1)}^n a_0$ is a primitive root of $p$ as well. $\blacksquare$

#### Finding Minimal r such that $x^r \equiv \text{integer} (mod \: f(x), \: p)$

Let's show we don't need to test r conditions, saving considerable time.

Lemma. Suppose that r has prime factorization, $r = p_1^{e_1} \ldots p_k^{e_k}$ If $x^{r \over {p_i}} \not\equiv \text{integer} (mod \: f(x), \: p) \quad \forall i \quad 1 \le i \le k$ then $x^m \not\equiv \text{integer} (mod \: f(x), \: p) \quad \forall m \lt r$

Proof. Assume to the contrary that there is some m < r for which $x^m = \text{integer} (mod \: f(x), \: p)$ Let $gcd( m, r ) = d$ then by Euclid's algorithm there exist integers u and v for which $d = u m + vr$ yielding $x^d = x^{u m + v r} = (x^m)^u(x^r)^v = \text{integer}$ Now consider $x^{r \over p_i} =(x^d)^{r / d \over p_i}$ Since $d | r$ , $r \over d$ is an integer. But d is the greatest common divisor of m and r, where m < r, so d < r also. Thus $r \over d$ contains at least one factor $p_i^k \text{for} k \ge 1$ for some $i$ making ${r / m} \over p_i$ an integer. But then $x^{r / p_i} = (x^d)^\text{integer} = \text{integer} (mod \: f(x), \: p)$ for some $i$, which is a contradiction. $\blacksquare$

Theorem. Factor r into primes, $r = p_1^{e_1} \ldots p_k^{e_k}$ The k+1 conditions $$x^{r / p_i} \not\equiv \text{integer} (mod \: f(x), \: p) \quad \forall \: 1 \le i \le k$$ $$x^r = \text{integer} (mod \: f(x)$$ hold iff $r\ge 1$ is the smallest number for which $x^r = \text{integer} (mod \: f(x), \: p)$

Proof. Let's take the easy direction first. If r is the smallest number for which $x^r \equiv \text{integer} (mod \: f(x), \: p)$ then it's intuitively obvious that $x^{r \over p_i} \not\equiv \text{integer} (mod \: f(x), \: p)$ Now take the hard direction. Assume all k+1 conditions hold. By the lemma, $x^m \not\equiv \text{integer} \: (mod \: f(x), \: p) \: 1 \le m \lt r$ and by assumption we had $x^r \equiv \text{integer} (mod \: f(x), \: p)$ $\blacksquare$

#### Testing if a Polynomial is Primitive

We'll tie together all the theory here. But first, we need a few more theorems.

Theorem. For $q \gt 2$ if $q | (p-1)$ it implies $a^q$ is not a primitive root of $p$ for any integer $a$.

Proof. By Fermat's theorem, if a isn't a multiple of p, $a^{p-1} \equiv 1 \: (mod \: p)$ But $q | (p-1)$ so for some $s \lt p-1$, $p-1 = q s$ giving $1 = a^{p-1} = a^{qs} = (a^q)^s$ Thus $a^q$ cannot be a primitive root of $p$. In the case $p | a$ we'd have $a^q \equiv 0 \: (mod \: p)$ so again $a^q$ is not a primitive root of $p$. $\blacksquare$

Theorem. Suppose $p_i | (p-1)$ where $p_i \ge 2$ If $x^r \: (mod \: f( x ), p)$ is an integer and $a$ primitive root of $p$, then $x^{r \over {p_i}} \not\equiv \text{integer} \: (mod \: f(x),p)$

Proof. Suppose $x^{r \over {p_i}} \equiv a\: (mod \: f(x),p)$ for some integer a. Then $x^r \equiv a^{p_i} \: (mod \: f(x),p)$ but the theorem above says $a^{p_i}$ is not a primitive root of $p$, a contradiction. $\blacksquare$

Theorem. Let the prime factorization of r be $r = {p^n - 1 \over p-1} = p_1^{e_1} \ldots p_k^{e_k}$ and let $f(x) = x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0$ where $0 \le a_i \le p-1$. Then $f(x)$ is a primitive polynomial of degree n modulo p iff the following conditions hold:

• (1) $x^r \equiv a \: (mod \: f(x),p)$ but the theorem above says $a^{p_i}$ for some integer $a$.
• (2) $x^{r \over p_i} \not\equiv \text{integer} \: (mod \: f(x),p)$ for $\forall i, 1 \le i \le k$ But we may skip this test for $i = i_0$ whenever $p_{i_0} | (p-1)$
• (3) The constant term in the polynomial satisfies $a \equiv (-1)^n a_0 \: (mod \: p)$
• (4) $a$ is a primitive root of $p$.

Proof. For the forward direction, assume f(x) is primitive. By the previous theorems, (1)-(4) hold. For the reverse direction, assume (1)-(4) hold. Conditions (3)-(4) together imply $a$ is a primitive root of $p$ and the minimality of $t$ as a power of $a$. By a previous theorem, f(x) is primitive. And by the theorem above, we can skip the test if $p_{i_0} | (p-1)$ for some $i_0$. $\blacksquare$

#### Finite Fields

• R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge University Press, 1994. Everything about finite fields.
• I. N. Herstein, Topics in Algebra, Second Edition, John Wiley, 1975. Introduction to abstract algebra.
• D. Burton, Abstract Algebra, Addison-Wesley, 1972. Another introduction.
• Fields and Galois Theory, J.S. Milne Online introduction to field theory.