Homepage of the libFES library

libFES :

Fast Exhaustive Search for Polynomial Systems over $\mathbb{F}_2$

libFES is a software library devoted to solving systems of polynomial equations over $\mathbb{F}_2$. As the name suggest, this is done by exhaustive search, and it is fast.

The city of Fès in Morocco

Introduction

libFES is a software library devoted to solving systems of polynomial equations over $\mathbb{F}_2$ by brute force. The current code is maintained by Charles Bouillaguet. Several people contributed to it (see below). The name libFES comes from the general idea behind the code: Fast Exhaustive Search. libFES can be used inside the Sage mathematics software, by installing an optional package. libFES is available under the General Public License Version 2 or later (GPLv2+).

This has nothing to do with the city of Fès (فاس‎) in Morroco. However, the leather tanning industry for which Fes was once renowned is a judicious illustration of the small-scale parallelism exploited in libFES.

Feature(s)

The libFES library has essentially one entry point, the solve function. Given a system of $m$ polynomial equations in $n$ variables over $\mathbb{F}_2$, solve returns its solutions, more-or-less interactively. It does so by trying all the $2^n$ possible combinations of the variables, and keeping the ones that are actually solutions.

While some other approaches are asymptotically faster, exhaustive search is usually much much faster in practice than any other technique, unless the system has a special structure that can be taken advantage of. See our benchmark below, and the related work section for more background.

The exhaustive search algorithm of libFES is described in this CHES'2010 paper. It improves the folklore methods by a polynomial factor and lends itself to extremely efficient implementations. This is one half of what makes libFES "Fast".

The other half is that a lot of effort has been put into optimizing the implementation. The main loop of libFES only evaluates the $m$ polynomials on all the possible $2^n$ candidate points, but it does so extremely fast. On a single core of a modern x86_64 CPU, libFES is capable of testing more than two candidates per CPU cycle!

Bragging Rights

This benchmark shows the time needed by several pieces of software to solve random, dense systems of $n$ quadratic polynomials in $n$ variables over $\mathbb{F}_2$. Of course, this comparison is biased in our favor, because random dense systems are essentially a worst-case for the other methods :). In a lot of interesting cases, the other methods may clearly outperform libFES.

benchmark

Using libFES

Basic use

The easiest way to use libFES is to use it from within the Sage computer algebra system. Starting with Sage version 5.7. libFES is available as an experimental extension package, which is not bundled with Sage by default. To install it, follow these (easy) steps:

  1. Install the experimental libFES package: sage -f fes
  2. Update the sage library: sage -b
  3. Use it:
    sage: from sage.libs.fes import exhaustive_search
    sage: R.<x,y,z> = BooleanPolynomialRing()
    sage: exhaustive_search( [x*y + z + y + 1, x+y+z, x*y + y*z] )
    
  4. Read the manual:
    sage: exhaustive_search?
    

Advanced use

You can obtain libFES's source code and do whatever you want with it. If your computer burns, we are not responsible. You may ask for help, again without any guarantee.

About libFES

Contributors

Other people contributed to the current code by writing early version. This includes "Tony" Tung Chou, Chen-Mou "Doug" Cheng, Hsieh-Chung "Kevin" Chen, Ruben Niederhagen and Bo-Yin Yang.

Release Notes

Related Work

Algorithms

Implementations

Future Plans

As of version 0.2, the most needed improvements are:

Contact

Please contact Charles Bouillaguet if there are bugs, questions, comments.

Valid XHTML 1.1