(fileVal "finiteField") indirectly yields powerful tools for arbitrary finite fields. This page grew with the development of the original code and provides the mathematical perspective, while the present page describes the code as accessed thru the repository. Let FF denote the Scheme value that (fileVal "finiteField") yields. The green text is a coherent synchronized interactive demo. It presumes fileVal.

For any prime p (FF p) yields Fp which depends on p and is a collection of tools for the finite field GF(p) among other things.

(define FF (fileVal "finiteField"))
(define F11 (FF 11))
(define F3 (FF 3))

• For various symbols op, (Fp op) yields an operation for GF(p). The symbols are m+, m-, m*, m/. Operands for these operators are merely non-negative Scheme integers less than p. m+ and m* are binary operators while m- and m/ are the additive and multiplicative unary inverse operators respectively. Warning: (m/ 0) => 0.

  ((F11 'm+) 6 7) ; => 2
  ((F11 'm/) 7) ; => 8

• Next comes GF(p)[X] which is the polynomial ring over GF(p). For other symbols op (Fp op) yields an operation for GF(p)[X]. Operands for these operators are Scheme vectors whose nth slot holds polynomial coefficient for Xⁿ; #(1 0 3) denotes 3X² + 1. The symbols are p+, p- and p*. Again p- is unary.

  ((F11 'p+) #(3 6) #(1)) ; => #(4 6)
  ((F11 'p*) #(1 1) #(1 1)) ; => #(1 2 1)

  ((Fp 'veq) a b) tests two polynomials for equivalence.

  ((F11 'veq) #(0 2 3 0 0) #(0 2 3 0)) ; => #t

  ((Fp 'trim) b) returns a polynomial equivalent to b but shorn of its leading zeros. A copy is made even if the leading term of b is not 0. Note that veq and trim do not depend on p.

  ((F11 'trim) #(0 2 3 0 0)) ; => #(0 2 3)

  ((Fp 'pqr) n d) yields (q . r) such that qd + r = n and the degree of r is less than the degree of d. Length of d must be > 0 and the high element of d must not be zero. Note absence of division; we only have a ring.

  ((F11 'pqr) #(3 6 5) #(3 1)) ; => (#(2 5) . #(8))
  ((F11 'pqr) #(2 2 1) #(1 1)) ; => (#(1 1) . #(1))
  ((F11 'pqr) #(2 2 2 2) #(2 2)) ; => (#(1 0 1) . #(0))

  ((Fp 'pgcmd) x y) returns the unique monic common divisor of highest degree, of polynomials x and y. The high order term of a monic polynomial is 1.

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

  ((Fp 'mexpt) u p f) returns the polynomial u^p modulo f. u and u are polynomials and p is a non negative integer.

  Routine (Fp '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 (Fp 'p->i) and (Fp 'i->p) translate to and from the dense ‘lexicographic’ integer coding of GF(p)[X].

  ((F11 'i->p) 0) ; => #()
  ((F11 'i->p) 8) ; => #(8)
  ((F11 'i->p) 11) ; => #(0 1)
  ((F11 'i->p) 122) ; => #(1 0 1)
  ((F11 'p->i) #(1 0 1)) ; => 122

  ((Fp 'gap) m) yields a stream generator, for the lexicographic stream of p^m polynomials of degree less than m. Streams are good when you can’t afford to finish generating all elements of a set before beginning to process them, as in searching for a irreducible polynomial.

  (ylppa (fileVal "stream") (lambda (sm si SG->lst lst->SG fs Cart string->SG)
  (map (F3 'p->i)
     (SG->lst ((F3 'gap) 2))))) ; => (0 1 2 3 4 5 6 7 8)

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

  ((F3 'gip) 2) ; => (#(2 2 1) #(2 1 1) #(1 0 1))
  ((F3 'tip) #(2 1 1)) ; => #t

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

  ((F11 'gfip) 6) ; => #(2 1 0 0 0 0 1) or X6+X+2

  When we have found an irreducible polynomial P of degree q in GF(p)[X] we can form a representation of GF(p^q) and ((Fp 'fops) P) returns tools for that finite field. Any finite field is isomorphic to some GF(p^q). Let Ff be the Scheme value produced by ((Fp 'fops) P) for some irreducible polynomial P.

  ((Fp 'gsip) m) is like ((Fp 'gfip) m) except for suspecting that it is exploring an irp desert whereupon it begins seeking irreducible trinomials.

  (((FF 6700417) 'gsip) 5) ; => #6(38 1 0 0 0 1) or X5+X+38

  When we have found an irreducible polynomial P of degree q in GF(p)[X] we can form a representation of GF(p^q) and ((Fp 'fops) P) returns tools for that finite field. Any finite field is isomorphic to some GF(p^q). Let Ff be the Scheme value produced by ((Fp 'fops) P) for some irreducible polynomial P.

  (define F11^6 ((F11 'fops) #(2 1 0 0 0 0 1)))

  • ((Ff 'f*) x y) returns the product of the polynomials x and y modulo polynomial P.
  • ((Ff 'f/) x) returns the multiplicative inverse in GF(p^q).

    ((F11^6 'f/) #(4 2 7 6 1 6)) ; => #(1 4 4 7 7 10)

  • ((Ff 'fexpt) b n) returns polynomial b raised to integer power n in GF(p^q).

    ((F11^6 'fexpt) #(4 2 7 6 1 6) 1000) ; => #(10 4 5 8 5 1)