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:

- Ordinary integers that come with Scheme,
- The integers modulo p form a field GF(p) and the routine gpa creates the arithmetic operators for it:
`m+ m− m* m/`. - Next comes the ring of polynomials over GF(p) and operators
`p+, p-, p*`. - 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

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`.

x

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 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.)

`(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

Some irreducible polynomials:

See HB Appl. Crypt for GF(2

For GF(3

For GF(3

GF(3

For GF(5

For GF(241

For GF(241

In general

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(2

External: automorphisms

Internal automorphism fragments: xx xx xx