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^{5}) 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

(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

Lets try for irps in the form X^{5} + 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

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

(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

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.