求解双基链的改进型贪心算法  

Greedy Algorithm of Convert Integers into Double-Base Chains

作　　者：李明[1] 王鲲鹏[1] 

机构地区：[1]中科院研究生院信息安全国家重点实验室,北京100049

出　　处：《微电子学与计算机》2010年第3期177-180,184,共5页Microelectronics & Computer

基　　金：国家"八六三"计划项目(2006AA01Z427);国家"九七三"计划项目(2007CB311201)

摘　　要：为了提升贪心算法的表现,更有效地求解整数的双基展开,文中采用了2-LineSearch方法,将树形分支结构引入了贪心算法.改进加速了贪心算法的收敛,使得在相同输入下,新算法返回的双基表达式的长度比普通的贪心算法减少了8%以上,在椭圆曲线标量乘法的计算代价方面也获得了至少2%的收益.In order to improve greedy algorithm so that it could convert integers into Double-Base Chains more efficiently, we introduce tree structure into greedy algorithm by taking advantage of 2-Line Search method. This improvement accelerates the convergence of greedy algorithm. Compared with the greedy algorithm, new algorithm gains more than 8% in the average length of double-base expansions and 2 % in the cost of scalar multiplication.

关 键 词：双基链 标量乘法 贪心算法 椭圆曲线密码 

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