2024年5月1日发(作者：)

华东师范大学

硕士学位论文

有限域快速多项式相乘运算核的研究

姓名：***

申请学位级别：硕士

专业：微电子学与固体电子学

指导教师：***

20050501

摘要

摘

要

有限域上的乘积运算是许多加密系统和编码理论的一种基本运算。有限域乘

法的运算效率在很大程度上决定了整个系统的性能。运算速度对于很多密码系统

来说至关重要，在一些密码系统里，其最主要的运算量来源于计算大量的有限域

整系数多项式的乘积。因此提高有限域整系数多项式乘法的速度对于这类密码系

统来说很有应用价值。

本文采用基于数论变换的算法结构，完成了有限域快速多项式相乘运算核的

设计及ＦＰＧＡ实现和测试验证，包括从算法设计、系统结构设计、各个子模块的

设计和实现、系统联调仿真到ＦＰＧＡ的下裁实现和测试整个流程。研究设计了一

种具有自主知识产权的高速、高精度的有限域多项式相乘运算核。提出了一种可

行的、易于硬件实现的结构，具有无误差、速度快、设计复杂度低的优点。在

Ｘｉｌｉｎｘ公司的１００万门的ＶｉｒｔｅｘｌＩ器件上实现，进行一次两个２５６点的有限域多

项式相乘仅需６５．４

ｕ

ｓ。和采用３台ＰＣ并行处理的软件实现方法相比，速度有２

倍的提高；和采用１台ＰＣ处理相比，速度有７倍的提高。可直接应用于数字签

名运算中。

本文有特色的主要工作如下：

１、

利用Ｆｅｒｍａｔ数变换（ＦＮＴ）的循环卷积性质进行整系数多项式相乘，

提高了运算的精度和速度。本文还利用迭代和多项式拆分相乘的技

巧，将高次幂多项式相乘转化为低次幂多项式相乘再进行迭加，克

服了ＦＮＴ运算点数的限制。并采用乒乓ＲＡＭ的结构提高运算能力，

得到流水线结构。

２、

采用类似基４ＦＦＴ的快速算法实现６４点ＦＮＴ。所设讨的ＦＮＴ模块

可并行处理两组数据。并具有可扩展的性能，可根据具体的要求实

现多组数据并行处理。

３、

采用新码码制进行ＦＮＴ运算。其中涉及的乘法运算和模运算均被方

便地转化为移位运算和加减法运算，有利于硬件实现。

４、

采用带进位的模加器和保留进位加法（ＭＣＳＡ）的结构提高ＦＮＴ和

模乘的处理速度并节省硬件资源。

５、

运算核采用ＶｉｒｔｅｘｌＩ系列ｘｃ２ｖ１０００．４ｆ９２５６实现，最高工作频率可达

到１００ＭＨｚ，完成一次运算所需的时间为６５．４

ｐ

ｓ。并将本运算核成

功地应用于有限域多项式幂运算中。

关键词：有限域，快速算法，多项式相乘，ＦＮＴ，模乘