有限域乘法器的性能分析与优化*

作者：梁田 日期：2008-12-26/span> 浏览：2972 查看PDF文档

有限域乘法器的性能分析与优化*

梁田
（浙江大学 超大规模集成电路设计研究所，浙江 杭州 310027）

摘要：评估分析了基于有限域的比特并行乘法器的常规结构的时间复杂度、空间复杂度和工作效率。并在此基础上，提出了更优化的精简结构比特并行乘法器，研究结果证明，在由三项式f(x)=xm+xk+1生成的域内，此优化结构的乘法器具有用m2的与门和m2－1的异或门衡量的最低的复杂度、最短的关键路径。此外，该结构还易于设计者使用硬件实现。
关键词：有限域；有限域乘法器；精简结构；系统优化
中图分类号：TN402；TN918.4文献标识码：A文章编号：1001-4551(2008)11-0009-03

Efficiency evaluation and optimization for bitparallel multiplier over finite field
LIANG Tian
(Institute of VLSI Design, Zhejiang University, Hangzhou 310027, China)
Abstract: The spatiotemporal complication and work efficiency for the regular structure of multiplier over finite field were evaluated. Furthermore, a reduced structure for the bitparallel multiplier was proposed. The experimental results prove that the reduced structure has the shortest critical path up to date with m2 AND gates and m2－1 XOR gates compare with other proposals. Meanwhile, it is easy for a designer to implement the proposed multipliers into hardware for their regular structures.
Key words: finite yield; finite yield multiplier; reduced structure; system optimization
参考文献(References):
［1］ORLANDO G. Efficient Elliptic Curve Processor Architectures for Field Programmable Logic［D］. America： Department of Electrical Engineering, Worcester Polytechnic Institute,2002.
［2］MOON S, PARK J, LEE Y. A fast finite field multiplier architecture for high security cryptographic application［J］. IEEE Trans. Consumer Electronics,2001,47(3)：700-708.
［3］LIDL R, NIEDERREITER H. Introduction to Finite Fields and Their Applications［M］. New York: Cambridge University Press,1994.
［4］MENEZES A J, BLAKE I F, GAO X, et al. Applications of Finite Fields［M］. netherlands: Kluwer Academic Publishers,1993.
［5］顾震宇,曾晓洋,陈超,等.一种高效的可伸缩分组并行有限域乘法器及VLSI实现［J］.微电子学与计算机,2003（4）：50-56.
［6］袁丹寿,戎蒙恬,陈波.一种快速有限域乘法器结构及其VLSI实现［J］.微电子学,2005,35（3）：314-317.
［7］袁丹寿,戎蒙恬,陈波.一种并行的有限域乘法器结构［J］.上海交通大学学报,2005,39(4）：636-639,644.
［8］KOC C K, SUNAR B. Lowcomplexity bitparallel canonical and normal basis multipliers for a class of finite fields［J］. IEEE Trans. Computers,1998,47(3):353-356.
［9］HANKERSON D, MENEZES A, VANSTONE S. Guide to Elliptic Curve Cryptography［M］. Germany: SpringerVerlag,2004.