Here is a little theory, with proof outlines, for finite fields that might be helpful.

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 pq elements for some prime p and some positive integer q. This field is called GF(pq). 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(pq) 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.
There are pq equivalence classes and for each such class there is a unique polynomial of degree less than q in that class. We use that polynomial to represent the class. The routine egcd is the extended Euclidean algorithm which we use to compute the multiplicative inverse in GF(p).

(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

We encode polynomials as integer vectors. Coefficient of xi is in vector element i.
x5 + 2x4 + x + 3 <=> #(3 1 0 0 2 1)
If the max element of the vector is not zero, the length of the vector is more than the degree of the polynomial.

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 up modulo f where u, up 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 pm 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(pq)

p+ and p- work here. When f is an irreducible polynomial of degree q over GF(p) (fops f) returns a list (f* f/ pow q) that provide the multiplicative group for GF(pq) where (pow a b) is the efficient power ab in the field and q is the degree of the polynomial f. f* is the binary multiply of the field and f/ is the unary multiplicative inverse. The representation is modulo f.


(tntip p q r) is a diagnostic that forms the products of all monic polynomials of respective degrees q and r and verifies that tip judges all of them to be reducible.

(tiv p q) generates all polynomials but 0 in GF(pq) 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

Some irreducible polynomials:
See HB Appl. Crypt for GF(2n).
For GF(32) x2 + 1, x2 + x + 2, x2 + 2x + 2.
For GF(33) x3 + 2x + 1, x3 + 2x2 + 2, x3 + x2 + 2, x3 + x2 + x + 2, x3 + x2 + 2x + 1, x3 + 2x2 + 1, x3 + 2x2 + x + 1, x3 + 2x2 + 2x + 2.
GF(34): x4 + x + 2, and 17 more.
For GF(52): x2 + 2, x2 + 3, x2 + x + 1, x2 + x + 2, x2 + 2x + 3, x2 + 2x + 4, x2 + 3x + 3, x2 + 3x + 4, x2 + 4x + 1, x2 + 4x + 2.
For GF(2413): the first of many is x3 + 2.
For GF(2416): the first of many is x6 + 7.
In general (define (irps p q) (((gpa p) 'gip) q))

This paper considers the test.

It would be good to verify this claim.

Here we explore where the irreducible polynomials might be found.

Square root
Square root in GF(p)
C code for GF(2q) for q <64
External: automorphisms
Internal automorphism fragments: xx xx xx