Fast Exhaustive Search for Quadratic Systems in F2
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 CPU
The CPU-version called "libFES" by Charles Bouillaguet et. al. is available here.
Source Code GPU
The GPU-version requires CUDA (and a compatible GPU) to be installed and set up. To download the latest version of the GPU software do the following:
tar xzvf MQForceGPU-20180724.tgz
Run
Source Code FPGA
To download the latest version of the FPGA design 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.