Fast Exhaustive Search for Quadratic Systems in $$mathbb {F}_{2}$$ on FPGAs
Fast Exhaustive Search for Quadratic Systems in $$mathbb {F}_{2}$$ on FPGAs
复制标题
在 FPGA 上快速穷举搜索 $$mathbb {F}_{2}$$ 中的二次系统
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Bo
中科院分区：
文献类型：
--
作者：
Charles Bouillaguet;Chen;T. Chou;R. Niederhagen;Bo
2010 年，Bouillaguet 等人。提出了一种基于 F2 的多项式系统的高效求解器，以内存换取速度（BCC+10）。因此，图形处理单元 (GPU) 可以在 21 分钟内求解出 48 个变量的 48 个二次方程。我们想在本文中回答的研究问题是专门设计的硬件如何执行此任务。我们通过在可重新配置的硬件（即现场可编程门阵列（FPGA））上求解多元二次系统来找到答案。我们表明，尽管（BCC+10）中提出的算法比传统枚举算法具有更好的渐近时间复杂度，但就硅面积而言，它并没有更好的渐近复杂度。尽管如此，我们的 FPGA 实现消耗的能源比 GPU 同类产品少 20{25 倍。这是一个显着的改进，更不用说 FPGA 每单位计算能力的货币成本通常比 GPU 便宜得多。关键词。多元二次多项式、求解方程组、穷举搜索、并行化、现场可编程门阵列 (FPGA)
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)