Where are the Irreducible Polynomials?

There are long runs of reducible polynomials over GF(p) for particular p and degrees. The routine gfip here searches for irreducible polynomials (IPs) simplest first, or lexicographically. When seeking an IP for GF(6700417⁵) it seems to stall. For n < 5, GF(6700417ⁿ) has dense IPs of the form xⁿ+k. It turns out that there are very few if any IP’s of the form x⁵+k which the routine is programmed to exhaust before considering anything else. Searching the entire set of 6700417⁵ monic polynomials over GF(6700417) randomly yields frequent IPs. There are even abundant k’s for which x⁵+x+k is irreducible. There are many k’s for which x⁵+k is irreducible over GF(641) but not over GF(6700417). There is a pattern here that needs a theory.

For every prime p, and every positive integer q, there is a field with p^q elements. Two fields with just p^q elements are isomorphic to each other. The name of this field is GF(p^q). Either as a lemma to or a corollary of this theorem is the fact that there are irreducible polynomials over GF(p), of degree q for all q > 1. A polynomial is irreducible iff it is not the product of two other polynomials. In this note we call an irreducible polynomial an irp.

To compute in GF(p^q) we must find an irp over GF(p) of degree q. There is a fairly fast test for irps and there are always easily found irps as far as I know. There are, however, some substantial neighborhoods of polynomial space that are free of irps and avoiding these neighborhoods is necessary lest the search bog down.

I discovered an irp desert when I tried to generate GF(6700417⁵) with this program. That code called an older version of finiteField which swept over the degree 5 polynomials over GF(6700417) lexicographically.

(let* ((p 6700417)(q 5)(Fp ((fileVal "finiteField") p))(i->p (Fp 'i->p))(tip (Fp 'tip)))
   (let loop ((n (expt p q))(c 10000)) (or (zero? c) (and (tip (i->p n)) (i->p n))
       (loop (+ n 1)(- c 1)))))

Note that (i->p (expt p q)) produces the polynomial X^q over GF(p). This notation is more expressive than transparent. This program reports failure in several seconds. X⁵ + k is reducible for k < 10000. The obvious explanation is that there is some multiplication pattern that makes any polynomial of the form X⁵ + k reducible over GF(6700417). I have not found such a pattern. There are such binomial irps for other primes: X⁵ + 2 is an irp over GF(13001). Is there something peculiar about 6700417? For one thing 6700417 × 641 = 2³² + 1 which refutes a conjecture by Fermat. There are no irps over GF(13003) of the form X⁵ + k. We test X⁵ + k for random k’s:

(let* ((p 6700417)(q 5)(Fp ((fileVal "finiteField") p))(i->p (Fp 'i->p))(tip (Fp 'tip))
      (kg ((((fileVal "RC4") "sts") 'rbi) p))(b (expt p q)))
   (let loop ((c 10000)) (let ((n (+ b (kg))))(or (and (zero? c) 'desert)
     (and (tip (i->p n)) (i->p n))
       (loop (- c 1))))))

and this yields desert meaning that 10000 randomly chosen k’s produced no irps.

Lets try for irps in the form X⁵ + X + k:

(let* ((p 6700417)(q 5)(Fp ((fileVal "finiteField") p))(i->p (Fp 'i->p))(tip (Fp 'tip)))
   (let loop ((n (+ p (expt p q)))(c 10000)) (or (zero? c) (and (tip (i->p n)) (i->p n))
       (loop (+ n 1)(- c 1)))))

X⁵ + X + 38 is an irp over GF(6700417). I wonder if we can count on this! X⁵ + X + 3 is an irp over GF(13003).

Lets get a crude irp density estimate:

(let* ((p 6700417)(q 5)(Fp ((fileVal "finiteField") p))(i->p (Fp 'i->p))(tip (Fp 'tip))
      (kg ((((fileVal "RC4") "sts") 'rbi) p))(b (expt p q)))
   (let loop ((c 10000)(ic 0)) (let ((n (+ b (kg))))(or (and (zero? c) (list ic 'irps))
     (and (tip (i->p n)) (loop (- c 1)(+ ic 1)))
       (loop (- c 1) ic)))))

reports (0 irps) evidencing the initial desert. Changing (expt p q) to (+ p (expt p q)) above counts 2002 k’s for which X⁵ + X + k is an irp over GF(6700417). 20% is pretty good odds.

(let* ((p 13003)(q 5)(Fp ((fileVal "finiteField") p))(i->p (Fp 'i->p))(tip (Fp 'tip))
      (b (+ p (expt p q))))
   (let loop ((c p)(ic 0)) (let ((n (+ b c)))(or (and (zero? c) (list ic 'irps))
     (and (tip (i->p n)) (loop (- c 1)(+ ic 1)))
       (loop (- c 1) ic)))))

reports (2664 irps) of the form X⁵ + X + k in an exhaustive seqrch. Again about 20%. There are 1932 irps in form X⁷ + X + k which suggests an irp density of about 1/q, if you are not in a desert. (P.S. Gauß knew this.)

With the following we probe the irp density in the whole of the polynomial space:

(let* ((p 6700417)(q 5)(b (expt p q))
   (Fp ((fileVal "finiteField") p))(i->p (Fp 'i->p))(tip (Fp 'tip))
      (kg ((((fileVal "RC4") "sts") 'rbi) b)))
   (let loop ((c 10000)(ic 0)) (or (and (zero? c) (list ic 'irps))
     (and (tip (i->p (+ b (kg)))) (loop (- c 1)(+ ic 1)))
       (loop (- c 1) ic))))

finds 2038 irps. (in about 40 sec.) The deserts seem to be rare.