Documentation - Project LinBox

Finite Fields in LinBox

The purpose of this page is not to present LinBox Fields as a tutorial or a documentation will do it. We just want to provide a basic support to people interested in using LinBox Fields in the best and simplest way.

What kinds of Fields are in LinBox?

LinBox provides two kinds of finite fields:

• Prime Fields (Z/pZ)
• Extension Fields ( GF(p^n))

Each field comes from either extern libraries or Linbox directly.

Available Library plugins in LinBox:

• Givaro
• Ntl 
• LiDIA

What are the LinBox classes defining Fields ?

Through wrappers using external libraries:

• Givaro:

  • GivaroZpz<XXX> (XXX taken in {Std32, Std16, Log16})

    This is a template class defining a prime field with elements of type 32-bits integer with STD32 , 16-bits integer with STD16 and LOG16. The classes GivaroZpz<STD32> and GivaroZpz<STD16> use a classical modular arithmetic whereas GivaroZpz<LOG16> uses a totally tabulated arithmetic using a Zech Log representation.

  • GivaroGfq

    This class allows the user to define extension fields with elements of type "standard C" long . This class uses the Zech Log representation and so can only define extension field with a cardinality less than 2^16, since the Zech Log representation needs to tabulate some value.

• NTL:

  • UnparametricField<XXX> (XXX took in {NTL::zz_p, NTL::ZZ_p})

    This is a template class defining prime fields with elements of type "standard C" long with NTL::zz_p and multi-precision integer with NTL::ZZ_p (based on Ntl multi-precision numbers).

• LiDIA:

  • LidiaGfq

    This class allows the user to define extension fields with elements of type LiDIA polynomial. So this class represents elements of a field as polynomials and use polynomial arithmetic. The cardinality of field is not restricted but larger it is, the slower the arithmetic operations are.

Directly written in LinBox Library:

• Modular<XXX> (XXX taken in {uint16, uint32, LinBox::integer})

  This class is a template class defining prime fields where the elements take their type in the class passed in template parameter. Such a class needs to have the overloaded operator (%, =, ==, +, -, *, /, +=, -=, *=, /=) to be passed as template parameter. The class LinBox::integer allows one to use multi-precision arithmetic based on gmp library.

Genericity of LinBox Fields in the library?

Most of the functions and the objects of the LinBox library are templated by a field type. This allows to use any of fields defined in LinBox in a generic way. This is possible because each fields in LinBox is defined according to a field interface which sets names and functions in a Linbox field class. The field interface is defined in a class called "FieldArchetype" in the file /linbox/field/archetype.h in the library.

What is the efficiency of Linbox Fields in the Library?

These performances have been obtained with these features:

Z/pz:

• p = 40493 for Simple Precision Arithmetic.
• p = 8191 for Totally Tabulated Arithmetic.
• p = 1267650600228229401496703301361 for Multi Precision Arithmetic (about 100 bits).
• Axpyin used 2 vectors of size : 2000 (for simple precision) and 100 (for multi precision).
• Dense Au (product of a matrix and a vector) used one matrix of size 700*700 (for simple precision) and 200*200 (for multi precision). and one vector of size 700 (for simple precision) and 200 (for multi precision).
• Sparse Au used the Trefethen matrix (20000*20000 with approimatively 555000 non-zero elements) and one vector of size : 20000.
• Dense A*B (product of two matrices) used two matrices of size 100*100 (for simple precision) and 20*20 (for multi precision).

GF(p^n) :

• p = 17 and n = 4 for Zech Log Arithmetic.
• p = 17 and n = 6 for Polynomial Arithmetic.
• Polynomial arithmetic: For each test, the same dimension as a prime field with multi precision arithmetic were used.
• Zech Log arithmetic: For each test, the same dimension as a prime field with simple precision arithmetic were used.