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(67004175) it seems to stall. For n < 5, GF(6700417n) has dense IPs of the form xn+k. It turns out that there are very few if any IP’s of the form x5+k which the routine is programmed to exhaust before considering anything else. Searching the entire set of 67004175 monic polynomials over GF(6700417) randomly yields frequent IPs. There are even abundant k’s for which x5+x+k is irreducible. There are many k’s for which x5+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 pq elements. Two fields with just pq elements are isomorphic to each other. The name of this field is GF(pq). 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(pq) 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(67004175) 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 Xq over GF(p). This notation is more expressive than transparent. This program reports failure in several seconds. X5 + k is reducible for k < 10000. The obvious explanation is that there is some multiplication pattern that makes any polynomial of the form X5 + k reducible over GF(6700417). I have not found such a pattern. There are such binomial irps for other primes: X5 + 2 is an irp over GF(13001). Is there something peculiar about 6700417? For one thing 6700417 × 641 = 232 + 1 which refutes a conjecture by Fermat. There are no irps over GF(13003) of the form X5 + k. We test X5 + 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 X5 + 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)))))
X5 + X + 38 is an irp over GF(6700417). I wonder if we can count on this! X5 + 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 X5 + 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 X5 + X + k in an exhaustive seqrch. Again about 20%. There are 1932 irps in form X7 + 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.