for
but
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
but
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.
Here is an ultra-fast review of some basic results we'll need to use.
An integer a is defined to be a primitive root of the prime p if
for
but
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
but
The Phi or Totient function is defined by
and, for n > 1,
(number of integers between 1 and n-1 relatively prime to n).
(Integers a and b are relatively prime (coprime) if the greatest
Euler's Totient with upper and lower bounds.
for prime p.
In general, if n has the prime factorization
then
Example:
= number of integers between 1 and 17 relatively prime
to 18 = # {1, 5, 7, 11, 13, 17}
We have the bounds,
where the lower bound holds except for the number,
n = 2 3 5 7 11 13 17 19 23.
For our example, this is 4.239 ≤ φ ( n ) ≤ 18.
A more loose lower bound is φ ( n ) ≤ √ n for n ≥ 6.
If p is a prime and p does not divide a, then
and for any integer a,
For example,
Any finite field has
elements where n is 1 or greater and p is
prime.
All fields with the same number of elements are isomorphic.
A field with
elements is called Galois Field
The Galois field
is a quotient ring
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
is the set of polynomials
with addition and multiplication of
polynomials mod
and mod 3.
forms a cyclic group of order
under multiplication with the elements,
where the field element a is called a
generator of the group (or primitive element of the field).
Multiplication is defined by
For consistency, we define the zero
element of the field as
Zero is not a primitive element.
Example: We show that
is a primitive element of the field
by multiplying out powers of a.
The field element
is a primitive element iff
Thus, it's intuitively obvious there are
primitive elements.
In the example above,
has
primitive elements, and they are
Any field element a satisfies the equation,
and non-zero field elements satisfy,
Example:
Any polynomial
with coefficients in
obeys the identity
This implies, if
is any root of
in
then so are
Example:
is the smallest subfield of
It is the field of integers under modulo p
arithmetic.
is isomorphic to an element of
if it satisfies the equation,
For example, for a = 2x above,
The minimal polynomial
of a field element
in
is the unique polynomial of lowest degree which has
as a root and whose coefficients lie in
More precisely, the coefficients are allowed to be in
as long as they are isomorphic to elements of
Example:
is the minimal polynomial of
The conjugates of a field element
in
are the r elements,
where r <= n is the smallest integer for which
Example:
has r = 2 conjugates,
and
because
The conjugates of the field element
are exactly the roots of the minimal polynomial for
The minimal polynomial can then be written explicitly as,
Example: The minimal polynomial,
factors as
In the cyclic group
of order
the element
is a generator if and only if s and N are relatively prime.
That is why
were primitive elements of the field
There are
generators.
Suppose we are given a set S and m of its subsets,
Let
denote the number of elements in a set S.
Then we have the formula,
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
m = 9, and let
be the set of multiples of i+1 except itself.
Then
,
,
,
and
through
are empty.
and
All other intersections are empty as are all intersections
of 3 or more sets.
The inclusion and exclusion principle then gives us
which agrees with the direct calculation,
f(x) is a primitive polynomial iff the field element x generates the
cyclic group of non-zero field elements of the finite field.
where p is prime and
In particular, as a generator of the non-zero field elements, f(x) satisfies the equations
but
for
The probability that a random f(x) is a primitive polyomial is
which is bounded above and below by
Lower bound factor in parentheses.
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 (pn-1)/(p-1). For a primitive polynomial of degree 9 modulo 3, we test 2 conditions instead of 19,682: (39-1)/(3-1) = 23 * 757. Or for degree 10 modulo 2, we can test 3 conditions instead of 1023.
Step 0) Factor
into distinct primes:
Step 1) Generate a new nth degree monic polynomial (randomly or sequentially)
of the form,
where we take care that all
possible combinations of coefficients are generated exactly once.
Step 2) Check that
is a primitive root of the prime p.
Use the quick test that a is a primitive root of prime p iff
for all prime
Of course,
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
When
63.2% of polynomials will have linear factors and be rejected.
Step 4) Check if
for some integer
Most polynomials are rejected here.
Step 5) 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/2n and 1/n.
Step 6) Check
Step 7) Check
for
But skip the test for
Step 8) If the polynomial f(x) passes tests in steps 1-7, stop. It is a primtive 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 xn mod f(x), modulo p on the coefficients, but is still much faster than attemping to use the definition of primitive polynomial directly.
We use Mathematica to demonstrate the technique for finding a primitive polynomial of degree n = 4 modulo p = 5.
You can download the Mathematica notebook or view the corresponding Mathematica PDF file; this Mathematica notebook is distributed under the terms of the GNU General Public License.
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 of the field element of the field
where p >=2 is prime and n > 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
for some m,
Then there is an h(x) such that
Since f is a minimal polynomial of a, it has a as a root:
so
contradicting the primitivity of a because its order is not maximal.
By Fermat's theorem for fields, the non-zero field element x satisfies
so x is a generator of the field, and f(x) is a primitive polynomial.
Theorem. The minimal polynomial f(x) of the primitive element a has the explicit formula,
where the roots of f(x) are the n conjugates of a.
Proof. By the minimal polynomial formula,
where r is the least integer such that
But a is a primitive element, so all the powers of a are distinct, until by
Fermat's theorem for fields,
Thus r=n.
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
i.e. it generates the field. x is a root because
By the polynomial field identity, the powers of x,
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.
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.
Theorem.
For any primitive polynomial f(x),
If f(x) has zeros in GF(p), it would contains linear factors,
contradicting irreducibility.
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
if
then
The same result holds if we replace the condition "= 1" with the condition "= integer".
Also, for any integer a and prime p, if n is the smallest number for which
and
then
Proof. Since n is the smallest such number,
so by the division algorithm,
which gives
But since r < n, this would contradict the minimality of n unless r=0.
Thus
The same exact reasoning based on minimal order holds for the other two conditions.
Theorem. Let r be the smallest number for which
for some integer a and let k be the smallest number for which
(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
then
Proof.
Observe
By the lemma,
But since 1 is an integer, by the lemma, we must have
From these divisibility results, we can write for some integers u and v,
giving
and by cancellation,
But then
By the lemma,
But we already had
from t=uv, so t=v, implying u=1 implying
Corollary. Given the definition of the numbers r and t as in the lemma above, if
and
then
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
and
Proof. Since f(x) is primitive,
Now our first theorem says
Next, by Fermat's theorem,
so by the lemma,
and then for some s,
Combining all of this,
Upon cancelling t,
Now we show
which will force the equality
and prove the first part of the theorem.
A field element,
is an element of
iff its p-1 power is 1.
by the primitivity of f(x), proving
By the lemma,
The value of t is
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
for some integer a is
The smallest value of t such that
is
In other words a must be a primitive root of p.
Theorem. Let f(x) be a primitive polynomial of degree n, modulo p.
The the constant term of f is
Proof. By the lemma, the primitive polynomial can be written as
and as the minimal polynomial
Multiplying out and comparing constant terms gives
which by geometric progression is
Corollary.
where a is the integer of the theorem earlier.
Also, a is a primitive root of p.
Proof.
Thus
But a is a primitive root of p by the theorem, so
is a primitive root of p as well.
Let's show we don't need to test r conditions, saving considerable time. We need two lemmas to get started.
Lemma. Suppose
for some m
If
then
Proof. Suppose that
and force a contradiction.
Since m divides r its prime factorization is
with
But since
there is at least one i for which
Making
So for some i, we get
a contradiction.
Lemma. Take the other case now and assume m does NOT divide r where
If
then
Proof. Since m is less than r and doesn't divide it, m and r must be relatively prime.
By the Euclidean algorithm,
so we can find integers u and v such that
Raising x to this power gives,
Now if
we'd get a contradiction since that would make x an integer, so any integral power
of x would be an integer; in particular,
We conclude
Theorem. Factor r into primes,
The k+1 conditions
hold iff
is the smallest number for which
Proof. Let's take the easy direction first. If r is the smallest number for which
then it's intuitively obvious that
Now take the hard direction. Assume all k+1 conditions hold.
By the lemma,
for
By the second lemma,
for
covering all possible m.
and by assumption we had
We'll tie together all the theory here. But first, we need a few more theorems.
Theorem.
For
if
it implies
is not a primitive root of p for any integer a.
Proof. By Fermat's theorem, if a isn't a multiple of p,
But
so for some s<p-1,
giving
Thus
cannot be a primitive root of p.
In the case,
we'd have
so again,
is not a primitive root of p.
Theorem. Suppose
where
If
is an integer and a primitive root of p, then
Proof. Suppose
for some integer a.
but the theorem above says
is not a primitive root of p, a contradiction.
Theorem.
Let the prime factorization of r be
and let
where
Then
f(x) is a primitive polynomial of degree n modulo p iff the following
conditions hold:
for some integer a.
for
But we may skip this test for
whenever
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
for some
Theorem. The number of primitive polynomials of the field
is
Proof. We need a few lemmas, but first, some notation. Let
be the primitive elements of the field.
They are precisely the generators of the cyclic group of non-zero elements of the field.
Let
be the primitive elements of the field.
They are precisely the generators of the cyclic group of non-zero elements of the field.
Let
Lemma.
Proof.
Suppose
By definition of conjugate, for some k,
But since
is a generator of the
group of non-zero field elements, the order of the generator,
and the size of the group,
must be relatively prime.
But
and
have no common factors, making
and
relatively prime as well.
Thus B is a generator and so
For the other direction,
suppose
Then
for some i, so
by definition.
Lemma. The sets of conjugates
are either disjoint or identical.
Proof.
Suppose
and let
and
have some common element B.
Then because B is a conjugate of both sets, for some u and v,
If we keep raising this equation to the pth power repeatedly modulo
the left side will cycle through all the elements of
and the right side will cycle through all elements of
Thus any element in one set is also in the other and they are identical.
Lemma. The number of distinct
is the number of primitive polynomials.
Proof. A primitive polynomial is the minimal polynomial of a generator, and its roots are conjugates of the generator.
So (number of primitive
polynomials) = (number of distinct minimal polynomials of all the generators) =
(number of disjoint sets of conjugate roots) =
(number of disjoint
conjugate sets
)
Lemma.
has n distinct elements.
Proof. See the earlier lemma which gives the formula for the roots of a primitive polynomial.
Proof of theorem.
Eliminate duplicate sets of conjugates and write
where the
are disjoint sets. It follows that
and the number of primitive polynomials is
Corollary. The probability that a randomly chosen polynomial f(x) of degree n modulo p is primitive is
and we have the bounds,
Proof. Use the fact that there are
total polynomials and the bounds on the Euler phi function.
When
about 63.2% of all polynomials have linear factors (zeros in GF(p)), and so are not primitive.
To check a polynomial for zeros quickly, we use Horner's rule to evaluate f(x) for x=0, 1 ... p-1.
Theorem.
The number of nth degree polynomials modulo p with no linear factors is
and
Proof. We'll use the principle of inclusion and exclusion.
Let S be the set of all monic nth degree polynomials modulo p.
There are p choices for each of the n coefficients, so
Now let
be the set of all nth degree polynomials having one or more factors of the form
(x-i), i=0,...,p-1.
A polynomial in this set has the form
There is one choice for the first factor, and
choices for the second factor giving
There are
possible sets
one for each choice of root i.
The set
is the set of nth degree polynomials containing both factors
(x-i) and (x-j) at least once.
An element of this set looks like
After picking i and j, there remain
choices for the coefficients, giving
The number of such sets is the number of ways of picking distinct
i and j from among p possibilities,
Similarly, there are
many sets for distinct i, j, and k whose cardinality is
At some point, the intersections become empty.
When
we run out of roots to use for linear factors,
and the last type of polynomial to consider has the form
It has only one set containing
polynomials.
On the other hand, if n < p, we end up factoring the polynomial completely:
There is only one polynomial of this type, but the set contains
elements.
Counting up the number of possibilities by the principle of inclusion and exclusion gives the formulas.
Example: Let n=3 and p=3.
By inclusion-exclusion, the number of polynomials with no linear factors is
Corollary. The number of polynomials of degree n modulo p with one or more linear factors is
Theorem. For the usual case of
we have
Proof. By the binomial theorem,
so
giving
Theorem. Pick an nth degree polynomial at random where
The probability that it has one or more linear factors is
Proof. The total number of polynomials is
Assuming each choice to be equally likely, the probability is
Lemma. The function
is an increasing function.
Proof. We'll show
Taking natural logarithms gives
Differentiating,
so
Since
we need only show
or, since
that
By definition of log base e,
Now we argue using the fact that
Area under the natural log curve.
the natural log is the area under the 1/t curve.
We'll show that
Area B is too hard to handle directly, so let's estimate it.
The curve 1/t is concave upward since its second derivative is
Thus C > B.
But C = (1/2) x base x
height =
Putting it all together,
Corollary.
Is a decreasing function for
Theorem. For
we have the bounds
Proof. From calculus,
Giving
By the corollary, P(n,p) decreases with increasing p, so it stays within the limits above.
However, it decreases very slowly: P(n, 4) = 0.684, P(n, 100) = 0.634 and
P(n, 500) = 0.632, close to the limiting value of 0.632120559...
We explain the theory behind testing a polynomial f(x) in modulo p arithmetic for reducibility; in particular, finding out whether it has two or more distinct irreducible factors.
We use a modification of the Berlekamp method for factoring polynomials over a finite field.
Differences are that
So the standard proof will need to be modified.
Any monic polynomial f(x) factors into the product of r distinct
irreducible polynomials,
If
then f(x) is reducible and can be rejected as a candidate for a primitive polynomial.
So how to find r? The trick, discovered by Berlekamp, is to find a congruence equation based on the Chinese Remainder theorem for polynomials whose solutions give us information about the number of factors.
Theorem. The two sets,
and
are the identical.
By the Chinese remainder theorem for polynomials, the set
has
solutions, but we can't find r because we don't know the irreducible factors.
But the set
is more tractable as we shall see.
Proof.
because by the Chinese remainder theorem for polynomials,
there is a unique v(x) for any given r integers,
so there are
solutions.
because 0 and 1 are solutions.
To prove equality, if
then by Fermat's theorem,
so that
On the other hand, if
then
so using the identity,
we get
Since the ring of polynomials is a UFD, we can factor each factor into the product of unique monic irreducible polynomials as
where
and some of the
could be zero.
Comparing factors, we have
For
we cannot have
and
simultaneously because we'd get
and
implying
leading to
which implies, since the polynomial is > 1,
a contradiction. Thus if
the sum collapses to one term,
for some j and
for some j.
Thus for all i,
for some j implying
But S2 = S1, so let's find
how many solutions v(x) solve the equation of S2 to get
Theorem.
iff
where
and
and
Proof.
and
But in a field of
characteristic p, we have the polynomial identity,
and so we have
Comparing equations, we have
iff
or
The number of elements in the set
is the number of solutions v to matrix equation,
or equivalently
The number of solutions = number of linear combinations of the basis vectors in
the left nullspace of Q-I
with weighting factors in GF(p).
This number is
Now we finally find r which is then
= # basis vectors of left nullspace of (Q-I).
A column reduction by Gaussian elimination using mod p arithmetic will reduce Q-I to column-echelon form.
This will not change the rank or nullity, being equivalent to a series of multiplications by non-singular elementary matrices.
One can read off the rank of the n x n column-echelon form matrix by counting the number of pivotal elements in the columns.
By Sylvester's theorem of linear algebra, rank + nullity = n, and upon applying this to the transpose of a matrix, Nullity of left nullspace = n - rank.
There is a better method for finding all primitive polynomials. Here is a brief sketch. Thanks to Martin Dowd for pointing out that better methods exist.
Copyright © 1986-2008 by Sean Erik O'Connor. All Rights Reserved. last updated 05 Jun 08.
Home
Up