OKlibrary  0.2.1.6
FiniteFields.hpp File Reference

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:
    1. The purpose is to provide the ability to specify the field together with the operation.
    2. While the underlying gf-functions rely on globally setting the field (once).
    3. So within a given block, our convenience "egf"-functions can be used to specify the field, while after this the original gf-functions 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.
    1. 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.
    2. 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.
    1. The unknown is always "x".
    2. 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:
    1. Inputs of the functions are integral polynomials in the unknown x, interpreted as representing the class of all equivalent polynomials.
    2. 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 (2-element) 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,5-2*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 field-elements are just represented by integer polynomial, only the special matrix-operations 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^2-x,x^2-x+1])
    mat1_inv : egf_matinv(gf27,mat1);
      matrix([-x^2-x+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 "non-extended", 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 implementation-defined. 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 {-(p-1), ..., 0, ..., p-1} 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 default-value is false).

Problems

  • Currently (Maxima version 5.15) the following gf-functions to not work properly:
    1. If largefield is set to false, then gf_set doesn't work anymore.
    2. findprim, primep don't work with prime-fields.
    3. ord doesn't seem to work at all.

Definition in file FiniteFields.hpp.