OPENF4 Documentation

Introduction

The openf4 library is a free (GPLv3) C++ implementation of the F4 algorithm.

It is efficient on prime fields of characteristic lower than 2^32 and on GF(2) extensions of degree less than 64.

Computations over prime fields of characteristic higher than 2^32 are available through a Givaro wrapper for arithmetic.

Computations over non prime fields (exept GF(2^n) with n<64) are not handled.

Requirement

You need a compiler that support C++11. If it is not your default compiler replace ../configure by CXX=compiler ../configure.

Example: CXX=g++-4.9.2 ../configure.

If you want a parallelized version, you need to compile with g++ (clang does not support openmp).

For prime fields of characteristic higher than 2^32 you need Givaro and GMP (required by Givaro). GMP must be compile with C++ support (–enable-cxx option in configure).

For some very specific systems the library can use FFLAS-FFPACK to improve slightly the time complexity (but increase in the same time the memory requirement).

Installation

Develloper version

Clone git repository: git clone https://github.com/nauotit/openf4.git

Basic installation (without Givaro and FFLAS-FFPACK)

1. Download the openf4 archive: Download
2. Extract it: tar -zxvf openf4-version-number.tar.gz
3. Move into the archive directory: cd openf4-version-number
4. Run the classical commands:
   1. ./configure
   2. make
   3. make check
   4. make install (need the root rights to install in /usr/local)

Configure options

Default values are in uppercase.

1. –enable-optimisation=YES/no (Use -O3 -funroll-loops -ftree-vectorize)
2. –enable-vectorisation=YES/no (Use -march=native, SSE2 or SSE4 can be used)
3. –enable-debug=yes/NO (add -g and remove -DNDEBUG)
4. –enable-openmp=YES/no (Use -fopenmp for parallelisation)
5. –help gives other informations (especially for external package paths)

Installation (with Givaro)

1. If Givaro is installed in the classical /usr or /usr/local: replace ./configure by ./configure –with-givaro
2. Else give the path to Givaro and GMP directories: replace ./configure by ./configure –with-gmp=/path/to/gmp –with-givaro=/path/to/givaro

Installation (with Givaro and FFLAS-FFPACK)

This support allows sometimes a small improvement but increase the memory requirement. FFLAS-FFPACK requires BLAS (we advise Openblas), Givaro and GMP. The Blas library must be compiled without threading (for Openblas compile with make USE_THREAD=0) in order to use FFLAS-FFPACK in multithread mode. Finally FFLAS-FFPACK may be configured with the following options: ./configure –enable-optimization –enable-openmp –with-gmp="/path/to/gmp" –with-givaro="/path/to/givaro" –with-blas-libs="-L/path/to/openblas/lib -lopenblas -Wl,-rpath=/path/to/openblas/lib"

1. If GMP, Givaro, Openblas, FFLAS-FFPACK are installed in the classical /usr or /usr/local: replace ./configure by ./configure –with-givaro –with-fflas-ffpack
2. Else give the different paths: replace ./configure by ./configure –with-gmp=/path/to/gmp –with-givaro=/path/to/givaro –with-blas-libs="-L/path/to/openblas/lib -lopenblas -Wl,-rpath=/path/to/openblas/lib" –with-fflas-ffpack="path/to/fflas-ffpack"

Tutorials

In these tutorials, we assume that the openf4 library has been installed in /usr or /usr/local. The input polynomials must not have several terms with the same monomial.

Tutorial for prime finite fields with modulo < 2^32

Tutorial for prime finite fields with modulo > 2^32

Tutorial for the GF(2) finite fields

Tutorial for GF(2^n) finite fields with n<64

If the library has been installed in a directory called "LIB" (using for example ./configure –prefix=/home/miscellaneous/LIB) add:

1. -I/home/miscellaneous/LIB/include
2. -L/home/miscellaneous/LIB/lib -lopenf4 -Wl,-rpath=/home/miscellaneous/LIB/lib

For instance tutorial-method2.cpp can be compiled with: g++ tutorial-method2.cpp -I/home/miscellaneous/LIB/include -o test -std=c++11 -L/home/miscellaneous/LIB/lib -lopenf4 -Wl,-rpath=/home/miscellaneous/LIB/lib

Bugs

Here is a list of encountered problems with their solutions:

Bug with libgomp and libstdc++ (make check failed)

Bug "Input polynomials must not have two different terms with the same monomial"

The computer freeze

If you find an other runtime bug:

1. Configure the project with: ./configure –enable-debug=yes
2. Run again you program
3. Get the bug repport address with ./configure –help
4. Send a program allowing to reproduce the error and the error itself.

Developper corner

Contribution is welcome, we give here some ideas of improvement but feel free to implement your own.

Improvement ideas

In order to keep consistency we follow these naming conventions:

Naming conventions