Improved algorithm of finite field multiplication in optimal normal basis

doi:10.3778/j.issn.1002-8331.2008.23.019

Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (23): 62-64.DOI: 10.3778/j.issn.1002-8331.2008.23.019

• 理论研究 • Previous Articles Next Articles

Improved algorithm of finite field multiplication in optimal normal basis

WANG Jin-rong^1,2

1.School of Information Science & Engineering，Hangzhou Normal University，Hangzhou 310036，China
2.College of Computer Science，Zhejiang University，Hangzhou 310027，China

Received:2007-10-16 Revised:2007-11-27 Online:2008-08-11 Published:2008-08-11
Contact: WANG Jin-rong

一种基于优化正规基的域元素乘法改进算法

王金荣^1,2

1.杭州师范大学信息科学与工程学院，杭州 310036
2.浙江大学计算机科学与技术学院，杭州 310027

通讯作者: 王金荣

Abstract

Abstract: Firstly，this article has discussed finite field multiplication，and given its general formula in optimal normal basis.Then，the authors has researched the Rosing algorithm and Ning-Yin algorithm，and put forward an improved algorithm and three precomputation methods.Finally，the author has tested all above algorithms.According to the analysis and experimentation，the new improved algorithm improves in its efficiency with about 20% by comparison with Ning-Yin algorithm.

Key words: ECC, optimal normal basis, finite field multiplication

摘要： 首先讨论了基域GF（2^m）上域元素的乘法运算，给出了优化正规基下乘法的一般计算公式。然后深入研究了Rosing和Ning-Yin算法，提出了一种改进算法和三种预计算方法。最后，分析和测试结果表明该改进算法比Ning-Yin算法提高了约20%。

关键词: ECC, 优化正规基, 域元素乘法

WANG Jin-rong^1,2. Improved algorithm of finite field multiplication in optimal normal basis[J]. Computer Engineering and Applications, 2008, 44(23): 62-64.

王金荣^1,2. 一种基于优化正规基的域元素乘法改进算法[J]. 计算机工程与应用, 2008, 44(23): 62-64.

[1]	XU Yong1, LIU Fen2. Research of scheme for preventing man-in-middle attack in heterogeneous sensor networks [J]. Computer Engineering and Applications, 2018, 54(22): 99-106.
[2]	LAI Zhongxi, ZHANG Anjie, ZHANG Zhanjun. Improved algorithms for computing 7P and 7kP on elliptic curves [J]. Computer Engineering and Applications, 2016, 52(1): 29-32.
[3]	RAN Pei, YANG Jiyun, TAN Jinyong. New protection scheme for integrity of Word electronic document [J]. Computer Engineering and Applications, 2013, 49(13): 76-79.
[4]	LI Haifeng1, LAN Caihui2, ZUO Weiping1, MA Haiyun1. ID-based threshold group signature scheme without trusted party [J]. Computer Engineering and Applications, 2012, 48(32): 89-93.
[5]	MI Junli1，LI Subei1，ZHANG Jianzhong2. ID-based proxy signature scheme without trusted center [J]. Computer Engineering and Applications, 2011, 47(26): 83-85.
[6]	XU Kaiping1，ZHENG Hongyuan1，LIU Jinfeng2，GU Jingjing1. Study on fast method of scalar multiplication in elliptic curve cryptography [J]. Computer Engineering and Applications, 2011, 47(15): 112-115.
[7]	TONG Lian，QIAN Jiang . Scalar multiplication algorithm against SPA and DPA attacks in ECC [J]. Computer Engineering and Applications, 2010, 46(35): 72-74.
[8]	LU Jie-ru,SU Bing. Design of supporting ECC digital certificate in IKEv2 authentication [J]. Computer Engineering and Applications, 2009, 45(2): 106-108.
[9]	ZHANG Jun-hong^1,2,CHEN Xin-meng¹. Kind of key agreement in electronic commerce [J]. Computer Engineering and Applications, 2008, 44(7): 139-140.
[10]	FU Mao-sheng^1,2,LUO Bin¹. （t，n） threshold secret sharing scheme without SDC based on ECC [J]. Computer Engineering and Applications, 2008, 44(32): 85-86.
[11]	YANG Min¹,MENG Qing-shu²,ZHANG Huan-guo². Construction of error-correction cryptosystem based on ECC and HFE [J]. Computer Engineering and Applications, 2008, 44(27): 31-32.
[12]	QIN Fan,DAI Zi-bin . Design and implementation of modular inversion for elliptic curve over finite prime field [J]. Computer Engineering and Applications, 2008, 44(23): 117-119.
[13]	LIU Wen-bo,ZHANG Fan,GUO Yun-fei,LIU Li-xiong. Research on optimal techniques for software implementation of ECC over F₂^m field [J]. Computer Engineering and Applications, 2008, 44(19): 28-30.
[14]	WANG Xu,QIAN Xue-zhong. Certificateless signature scheme provably secure in standard model [J]. Computer Engineering and Applications, 2008, 44(11): 129-132.
[15]	. (t, n) Threshold Key Escrow Scheme Based on Status-tree [J]. Computer Engineering and Applications, 2007, 43(4期): 146-149.

Improved algorithm of finite field multiplication in optimal normal basis

一种基于优化正规基的域元素乘法改进算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics