Chapter 1. Introduction

Table of Contents

Specializing code for a given field
Generalizing code for a large set of fields
Reporting bugs, comments, feature requests...

MPFQ is a software library intended for manipulation of finite fields. The announced objectives of MPFQ are both speed and usability. It is well-known that such objectives are hard to conciliate. We acknowledge a clear bias towards speed, since no concession is made in this regard. However the interface of MPFQ is expected to become sufficient for most intended uses.

The prominent strength of MPFQ is to deliver top-notch performance for finite fields of moderate size when some characteristics (e.g., modulus size) are known in advance. This is a very common application. Existing libraries so far offer the possibility to completely configure the finite fields used at runtime. For this reason alone, serious evaluation of the speed of an algorithm on a precise finite field often requires reimplementing the finite field layer.

MPFQ achieves good performance for predefined fields by providing automatically generated special-purpose code. A large portion of the MPFQ library is therefore written in Perl.

The two main targets of MPFQ are the Galois fields \(\mathbb{F}_{2^n}\) and \(\mathbb{F}_p\) with \(p\) prime. Extensions of prime fields of characteristic other than \(2\) will be supported at some point for completeness, but they are not the primary target for optimization.

Specializing code for a given field

An important feature of MPFQ is to allow the user to implement a specialization of a code in order to take advantage of optimizations that are available only for a field or a small class of fields. For instance, once you have an efficient implementation for prime fields for which the modulus fits in 2 machine words, you might have an application that deals with \(\mathbb{F}_p\) where \(p\) is a Mersenne-like prime for which a very fast reduction algorithm is available. Adding such an optimized reduction is not too hard in MPFQ, and you will get the full speed, since no test is done at runtime: you will have another C-type and new function names for this new field additionally to the previous general ones.

In principle, it is possible to add optimizations written in the C language or in assembly.