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

`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:
**F**ast **E**xhaustive **S**earch. `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`.

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!

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.

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:

- Install the experimental
`libFES`package:`sage -f fes` - Update the sage library:
`sage -b` - 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] )

- Read the manual:
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.

- You can get the code in a source tarball
- Clone our public git repository :
`git clone https://bitbucket.org/fes/fes.git` - You can browse the source, watch the changesets

- 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

**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

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

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.

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)

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