Fast Exhaustive Search for Quadratic Systems in F2 on FPGAs


Introduction

In 2010, we proposed an efficient solver for polynomial systems over F2 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 F2 on FPGAs".

Source Code

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

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.

Contact

Ruben Niederhagen