Fast exhaustive search for quadratic systems in F_2 on FPGAs

In 2010, Bouillaguet et al. proposed an ecient 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 processing unit (GPU) in 21 minutes. The research ques- tion that we would like to answer in this paper is how specically de- signed hardware performs on this task. We approach the answer by solv- ing multivariate quadratic systems on recongurable hardware, namely Field-Programmable Gate Arrays (FPGAs). We show that, although the algorithm proposed in (BCC+10) has a better asymptotic time complex- ity than traditional enumeration algorithms, it does not have a better asymptotic complexity in terms of silicon area. Nevertheless, our FPGA implementation consumes 20{25 times less energy than its GPU coun- terpart. This is a signicant improvement, not to mention that the mon- etary cost per unit of computational power for FPGAs is generally much cheaper than that of GPUs. Keywords. multivariate quadratic polynomials, solving systems of equa- tions, exhaustive search, parallelization, Field-Programmable Gate Ar- rays (FPGAs)