The code described below has been recast in repository form and has been further developed there. In particular see this. This page, however, retains the mathematical introduction.

This code generates finite fields and performs arithmetic therein. Any finite field has p^q elements for some prime p and some positive integer q. This field is called GF(p^q). Equinumerous finite fields are isomorphic. The only way I know to do arithmetic in a finite field is to choose a polynomial P of degree q that is irreducible over the field GF(p). Most polynomials are reducible but blind search works well if you have a fast reducibility test. The values of the field GF(p^q) are then represented by polynomials modulo P with coefficients in GF(p).

A Bit of Necessary Terminology and Theory

The coefficient of the high order term of a monic polynomial is 1. The coefficient of the low order term of an odd polynomial is not zero. (my terminology) The product of odd monic polynomials is odd and monic. Any reducible odd monic is the product of two odd monics.

There are four arithmetics in sight here that are not to be confused:

1. Ordinary integers that come with Scheme,
2. The integers modulo p form a field GF(p) and the routine gpa creates the arithmetic operators for it: m+ m− m* m/.
3. Next comes the ring of polynomials over GF(p) and operators p+, p-, p*.
4. Last (here) comes the field which results from choosing an irreducible polynomial P of degree q and establishing the equivalence relation between ring elements, p ≡ q iff p − q = rP for some polynomial r.

(gpa p) returns a procedural map from symbols to a bundle of routines each of which knows p.
((gpa p) 'op) returns routine op from the bundle.

GF(p) Operators in bundle

Operators m+ m- m* m/ are for GF(p)— m+ m* are binary while m- and m/ are unary operators. The values are standard Scheme integers—(((gpa 11) 'm-) 5) => 6.

Polynomial Ring Operators

Such polynomial representations are ‘vectors’ both in the terminology of the Scheme language, and also as members of a mathematical vector space over the field GF(p). Indeed the collection of such polynomials is an associative algebra.

The operators for the polynomial ring over the integers modulo p are p+ p- p*.

(trim b) returns a polynomial like b but shorn of its leading zeros. A copy is made even if the leading term of b is not 0.

The routine (pqr n d) finds quotient and remainder of two polynomials over GF(p). This Scheme code is in style of Fortran.
(pqr n d) => (q . r) such that qd + r = n and the degree of r is degree(d) − 1. Degree (length) of d must be > 1. The high element of d must not be zero. Note absence of division; we only have a ring.

(pgcmd x y) returns the unique monic common divisor of highest degree, of polynomials x and y.

(pegcd l s) yields (x . y) such that lx+sy = gcd(l, s) (=(pgcmd l s) the monic one!)

(mexpt u p f) yields u^p modulo f where u, u^p and f are polynomials, and p is a non-negative integer. Length of yield is one less than length of f.

Routine tip, tests a polynomial for being irreducible; every finite field needs an irreducible polynomial in order to represent field values. This is from Algorithm 4.69 of HB. of App. Cryptog.

Routines p->i and i->p translate to and from the dense ‘lexicographic’ integer coding of a polynomials over GF(p).

(gap m) yields an SG, for the lexicographic stream of p^m polynomials of degree less than m.

(gip m) returns the list of irreducible monic polynomials of degree m. This is feasible only for small m and p.

(gfip m) returns the lexicographically first irreducible polynomial of degree m.

(With fs, tip and gap, gip and gfip can be easily synthesized outside of gpa.)

Operators for GF(p^q)

Diagnostics

(tiv p q) generates all polynomials but 0 in GF(p^q) and verifies that an inverse can be computed. The first irreducible polynomial is used in each case.

Using sets of polynomials, Matrices of finite fields

This paper considers the test.

It would be good to verify this claim.

Here we explore where the irreducible polynomials might be found.