# 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.

# 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.

• Solving with a SAT solver is done in two phases: the polynomials are first converted to CNF, and the resulting SAT instance is fed to a SAT-solver. We tried both CryptoMiniSat 2.9.6 and Glucose 2.2. They run at comparable speed, but the latter uses less RAM. In both case, their running time is subject to a lot of variability.

• The implementation of F4 in the MAGMA computer algebra system (V2.19-1) is probably the best currently available. It could only be tested up to $n = 29$, afterwards it used more than the 74Gbyte of RAM that were available.

• Hybrid-F4 denotes the following algorithm: "guess" the value of $k$ variables, and solve the system of $n$ polynomials in $n-k$ variables using F4. The last step has to be repeated $2^k$ times. The optimal value of $k$ has been chosen.

# 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] )

sage: exhaustive_search?

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.

### Contributors

• Charles Bouillaguet: maintainer, wrote most of the current code
• "Tony" Tung Chou: wrote most of the code of an earlier version, and the current assembly generator
• Ralf Zimmermann: designed and implemented an efficient indexing scheme for boolean monomials
• Paulo César Pereira de Andrade: libtoolized the code
• Paul-Emile Boutoille: improved small-scale parallelization
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

• Version 0.2, September 2013: thanks to the work done by Paul Emile Boutoille during his internship, the quadratic solver is now twice faster.
• Version 0.1, June 2012: initial release, after an extensive effort in Taiwan by C. Bouillaguet, Tung "Tony" Chou and Ralf Zimmermann

### Related Work

#### Algorithms

• Besides exhaustive search, the main approach to solve polynomial systems over finite fields consists in computing a Groebner basis using Buchberger's algorithm or its modern variants such as F4 and F5. The complexity of this process is exponential in the number of variables, but depends very weakly on the size of the field. This means that Groebner basis algorithms outperform exhaustive search over large fields, but are at a disadvantage over small fields. Magali Bardet's PhD thesis suggests that the cutoff value is around $q=16$. Over $\mathbf{F}_2$, Groebner basis algorithms are asymptotically much worse than exhaustive search.

• Boolean polynomials have a simpler structure than full-blown polynomials (i.e., there are no exponents), and this makes it possible to write efficient code dedicated to manipulating boolean polynomials. This is what Michael Brickenstein and Alexander Dreyer have been doing in their PolyBori library. PolyBoRi is used inside Sage to create and deal with Boolean Polynomial Rings, and thus libFES relies on it. PolyBori also contains specialized versions of the slimgb algorithm and F4

• What has been called Hybrid solving, namely combining exhaustive search and a form of Groebner basis computation, can be asymptotically faster than exhaustive search over $\mathbb{F}_2$. After the values of sufficiently many variables have been guessed, Groebner basis algorithm become faster than exhaustive search. Jiun-Ming Chen and Bo-Yin Yang proposed in 2004 to "guess" $0.45n$ variables out of $n$, and to run the XL algorithm (an inferior form of modern Groebner basis algorithm such as F4 and F5), resulting in the first published algorithm beating the $2^n$ bound.

• In 2012, Magali Bardet, Jean-Charles Faugère, Bruno Salvy and Pierre-Jean Spaenlehauer invented a slightly more sophisticated algorithm that combines guessing variables, polynomial elimination and exhaustive search to reach an asymptotic complexity of $\mathcal{O}\left(2^{0.791n}\right)$. These results are mostly theoretical though, because these asymptotically fast algorithms are slower than exhaustive search for values of $n$ small enough for the computation to be possible in practice.

#### Implementations

• As far as we know, the best implementation of a Groebner basis algorithm is the version of F4 included in the (commercial) MAGMA computer algebra system. However, it is not freely available.

• Ruben Niederhagen and "Tony" Tung Chou implemented an early version of the algorithm implemented in libFES on GPUs. With this code, they could solve a system of 48 quadratic equations in 48 variables in only 21 minute on a single NVIDIA GeForce GTX 295 card.

• Ruben also implemented several solving algorithms on FGPA. He concluded that a quadratic system of 80 equations in 80 variables (thus offering "80 bits of security" in cryptographic terms) could be broken in practice with a custom-built supercomputer.

• Mate Soos has developped CryptoMiniSat, a successful SAT-solver and scripts to convert polynomial systems into instances of SAT. This technique can also be used inside Sage.

### Future Plans

As of version 0.2, the most needed improvements are:

• Improving the "check" part of the code, using bitslicing and a fast matrix transpose. This should speed up degree-3 in practice.
• Avoiding useless indices computation. It turns out that we never need to compute them! This should speed up high-degree enumeration.
• Improving the moebius transform algorithm to take cache sizes into account (and write assembly code)
• Parallelization (maybe just inside Sage)