## Fast Exhaustive Search for Quadratic Systems in F_{2} on FPGAs

### Introduction

In 2010, we proposed an efficient solver for polynomial systems over
F_{2} that trades memory for speed [BCC+10].
As a result, 48 quadratic equations in 48 variables can be solved on a graphics
card (GPU) in 21 minutes.
The research question that we would like to answer in this project is how
specifically designed hardware performs on this task.
We approach the answer by solving multivariate quadratic systems on
reconfigurable hardware, namely Field-Programmable Gate Arrays (FPGAs).
Our FPGA implementation consumes 20–25 times less energy than the GPU
implementation in [BCC+10].
This is a significant improvement, not to mention that the monetary cost per
unit of computational power for FPGAs is generally much cheaper than that of
GPUs.

We describe this project and the implementation in our paper
"Fast Exhaustive Search for Quadratic Systems in F_{2} on FPGAs".

### Source Code

To download the latest version of the software do the following:

tar xzvf forcemq-20130729.tgz

In the root directory forcemq-20130729/
you will find several Pyhton scripts and a Makefile.
The Makefile requires
iverliog in
$PATH and
will produce a simulator program
search
for a small system with *m*=12 equations and *n*=12 variables.
The system size can be modified via the
Makefile-variables
M and
N.

The directory forcemq-20130729/RIVYERA/ contains a Makefile to compile the design for the Spartan-6 FPGA in the RIVYERA FPGA cluster from Sciengines. The Makefile requires an installation of Xilinx ISE Design Suite and the SDK from Sciengines. Again, the system size can be modified via the Makefile-variables M and N.

For further details please refer to our paper.