User documentation for finite fields in Lisp/Maxima.
More...
Go to the source code of this file.
Detailed Description
User documentation for finite fields in Lisp/Maxima.
The Maxima package "gf", and simple wrappers

This finite fields manual documents the Maxima package.

Finite field functions within the OKlibrary provide simple convenience wrappers to basic functions of the underlying "gf" package:

The purpose is to provide the ability to specify the field together with the operation.

While the underlying gffunctions rely on globally setting the field (once).

So within a given block, our convenience "egf"functions can be used to specify the field, while after this the original gffunctions can be used.

For the basic functions from the
gf
package, which always have prefix "gf_", we provide "extended" versions with corresponding prefix "egf_", which just offers an additional first argument, specifying the field.

Finite fields are specified by a triple [p,n,m]:

p is a prime number;

n a natural number;

m an irreducible polynomial of degree n, in the unknown x and with integer coefficients understood modulo p.
The degree n is redundant and can be left out; and if only p is specified, then the prime field GP(p) is meant.

Such tuples are passed as the first argument to each of our function, to specify which field the operation should be performed in.

The field, simply denoted by GF(p^n), has as elements the congruence classes of polynomials modulo m.

The unknown is always "x".

To specify which of the finite fields GF(p^n) of order p^n we are speaking about, we use the notation "GF(p^n)_m", where m is the irreducible polynomial used.

Field elements are represented as follows:

Inputs of the functions are integral polynomials in the unknown x, interpreted as representing the class of all equivalent polynomials.

The output of the functions is again such an integral polynomial, but using a standard representation for the equivalence class.
So equality of field elements represented by polynomials p(x) and q(x) happens by first converting p(x), q(x) into their standard representations, for which then we can use ordinary equality testing.
Usage

Addition and multiplication of elements in GF(2)_x, a simple (2element) bit field with "xor" and "and" as the addition and multiplication operators:
egf_add([2,1,x],0,1);
1
egf_add([2,x],0,1);
1
egf_add([2,x],1,1);
0
g2 : [2,1,x];
egf_mul(g2,1,1);
1
egf_mul(g2,1,x);
0

The same additions, but using different representations (recall: here the polynomial x is equivalent to zero):
egf_add(g2,x,3+x^2);
1
egf_add(g2,52*x+x^4,7+6*x^10);
0

For converting a polynomial into the standard representation, use addition with 0:
egf_add(g2,0,x^3);
0
egf_add(g2,0,x^3+5);
1

Multiply two elements in GF(2^8)_(x^8+x^4+x^3+x+1), the "Rijndael byte
field" from ComputerAlgebra/Cryptology/Lisp/CryptoSystems/Rijndael:
egf_mul([2,8,x^8+x^4+x^3+x+1], x^5+x^3+x+1, x^7+x^3+x^2);
x^7+x^5+x^4+x+1
egf_mul(rijndael_byte_field, x^5+x^3+x+1, x^7+x^3+x^2);
x^7+x^5+x^4+x+1

Matrix operations use the usual Maxima matrix operations to generate the matrix (recall, the fieldelements are just represented by integer polynomial, only the special matrixoperations interprete them):
gf27 : [3,3,x^3+x^2+x+2]$
mat1 : matrix([0,1],[x,x+1])$
mat2 : matrix([x+1,x],[x,x^2])$
egf_matmul(gf27,mat1,mat2);
matrix([x,x^2],[x^2x,x^2x+1])
mat1_inv : egf_matinv(gf27,mat1);
matrix([x^2x+1,x^2+x+1],[1,0])
egf_matmul(gf27,mat1_inv, mat1);
matrix([1,0],[0,1])

Since our little wrappers call the underlying
gf_set
function with each call, after the first call one may just use the "nonextended", original versions (provided, the field didn't change): egf_add(g2,0,x^3);
0
gf_add(0,x^3);
0
To keep in mind

When using the matrix functions "egf_matmul" and "egf_matinv", the polynomials returned within the resulting matrix will be in an optimised form, called a "CRE" (Canonical Rational Expression). To convert such a polynomial back to a basic polynomial expression, for example for comparison of equality, one may apply the maxima function "totaldisrep" to the result, to regain the result with simple maxima polynomials. OK: this is completely unclear.

The polynomials returned by the field operations uniquely represent, as polynomials, the field element (for the same field element always the same polynomial, as polynomial over the integers, is returned). However which polynomial is chosen is implementationdefined. For example in the field with 27 elements:
gf27 : [3,3,x^3+x^2+x+2]$
egf_add(gf27,2,0);
1
egf_add(gf27,2*x,0);
x
egf_add(gf27,2*x^2,0);
x^2
egf_add(gf27,x^2,0);
x^2
The representation for characteristic p chooses the element from {(p1), ..., 0, ..., p1} with minimal absolute value.

By default, when setting a field then irreduciblity of the polynomial is not checked; checking can be enabled by setting
GF_IRREDUCIBILITY_CHECK
to true
(the defaultvalue is false
).
Problems

Currently (Maxima version 5.15) the following gffunctions to not work properly:

If largefield is set to false, then gf_set doesn't work anymore.

findprim, primep don't work with primefields.

ord doesn't seem to work at all.
Definition in file FiniteFields.hpp.