基于双基数子集表示的快速标量乘算法  

Fast scalar multiplication based on subset of double-base number system

作　　者：王圆圆[1,2] 殷新春[2] 

机构地区：[1]扬州职业大学信息工程学院,江苏扬州225009 [2]扬州大学信息工程学院,江苏扬州225009

出　　处：《江苏大学学报（自然科学版）》2009年第3期297-301,共5页Journal of Jiangsu University：Natural Science Edition

基　　金：国家"863"计划项目(2007AA012448);国家自然科学基金资助项目(60473012);江苏省六大人才高峰项目(06-E-025)

摘　　要：为了减少双基数表示时间,提出双基数子集的概念,将存储空间和预计算时间从n2降低到3n-2,同时给出求子集表示的贪婪算法.给出基于双基数子集的标量乘算法,由于搜索空间的降低,整数的双基数子集表示个数稍微多于双基数表示个数,新算法使用混合坐标进行优化.从运算量、存储空间上,将新算法分别与传统固定基点的窗口算法和Dimitrov的基于双基数链的算法进行比较,结果证明新算法显著优于前人算法.A new algorithm based on subset of double-base number system（DBNS） was proposed in order to improve the efficiency of scalar multiplication. The concept of subset of DBNS was described, and storagespaee and precomputation time were decreased from tz2 to 3n -2. A greedy algorithm was deduced to compute the DBNS chain at the same time. The number of 2-integers is smaller, so that the length of DBNS chain becomes a little longer. Mixed-coordinate was used to optimize the algorithm. The new rithm was compared with the traditional fixed-point window algorithm and Dimitrov method, and the resuits show that the new algorithm is more efficient in computation time and storage space than others.

关 键 词：密码 椭圆曲线 标量乘法 双基数系统 贪婪算法 混合坐标 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]