文档介绍：浙江大学学报理学版
第卷第期://..../ 【..
年月.
不可约三项式有限域的高速并行比特乘法器
李大为,龙彦辰,沈海斌
浙江大学超大规模集成电路设计研究所,浙江杭州
摘要:在移位多项式的弱共轭基底的理论推导的基础上,
不可约三项式,一生成的域内,此种结构的并行比特乘法器需要个与门和。
同样的空间复杂度下,时间复杂度降低为,—一,具有最短的关键路径.
关键词:有限域;移位多项式基底;弱共轭基底;不可约三项式;并行乘法器
中图分类号:;. 文献标志码: 文章编号:———
—, —,—,,
,
.
,,:—
: ,—
. ,;。
一, ,一,—
.
:; ;; ;—
期乘法器只针对素数域这一问题,此
引言后,大量高效的二元域上乘法和指数
,
有限域运算在计算机代数、组合设计、编码理论乘法器由等首
.
—
算法,为代表, 算法/乘法器,克服了其模块化程度和
由于其具有密钥短、安全性能高等优点,从而在信息规则度不高的缺点. 还给出了
,
是有限域除法、指数等运算的基础,因此,
法的快速实现与高速乘法器的设计是有限域运算研等发现了一个构建适
究的重要方面. 用于任意多项式乘法器的方法,既
前人提出了多种有效的有限域高速乘法器以及考虑了通常的情况,又考虑了特殊形式不可约多项
, 等成功地将式的情况,如三项式、全一多项式,一
乘法算法移植到二元域上,弥补了早、等距多项式,—
收稿日期:—.
作者简介:李大为一,男,博士研究生,主要从事信息安全技术研究
通信作者,—:....
浙江大学学报理学版第卷
, 等首次提出其中≤≤加一,
了移位多项式基底; ,域中的任意元素可唯一表示为一
的概念,并给出了传统型和型两种一一
, ⋯,以,以。.
基于的乘法器结构,与以往相比在时间复杂度
上大大优化. 在文献中已证明,的最优解是志或一,
在上述二元域不可约多项式乘法器研究工作的这样,元素可以容易的从转化为的表示形
一——一
基础上,本文提出了一种新的基底,∑∑升分别
基底的弱共轭基底;——一

,并据此提出了一种改进型的并行比特乘法器
、,可得到从到的转化.

抖,当一≤≤一—.
案做了进一步改进,为。,

一一. 一,当一≤≤一.
本文结构安排如下:第部分提出了基底的定从到的转化如下:
义并讨论了有限域运算的一些基础知识;第部分¨ 一~
一∑一∑一.∑一
给出了乘法器的具体实现方案及其优化措施;第一一一
部分对复杂性进行了分析,并将本文的设计方