摘要
通过对目前常用的几类模乘方法的综合研究,充分吸取估商型模乘算法的估商思想,借助Montgomery型模乘算法中模2n易计算特性,采用窗口分段处理方式,给出了一种新的利用模N进行预计算的方法,进而提出了一种新的加法型模乘AB mod N快速实现算法。模N为1 024-bit、窗宽为6时,新算法平均仅需693次1 024-bit加法便可完成一次AB mod N模乘运算,与当前加法型模乘算法相比,较大幅度地降低了计算复杂度。
Researched on several recently widely used modular multiplication algorithms, adopted the ideal of window division, estimating quotient, and modular 2^n easy to be calculated, which is used in Montgomery modular multiplication algorithm, a new fast calculating AB mod N algorithm based on addition is presented, which introduces pre-calculating by modular N. When the length of modular N is 1 024-bit and the length of window is 6, on the average, the new algorithm requires only 693 times 1 024-bit addition to calculate AB mod N. Comparing with current additional modular multiplication algorithm, the computing complexity is reduced largely.
出处
《计算机工程》
CAS
CSCD
北大核心
2007年第1期167-169,共3页
Computer Engineering
基金
浙江省自然科学基金资助项目(M603028)
浙江省教育厅高校科研计划基金资助项目(20030636)
关键词
公钥密码
模幂运算
模乘运算
窗口宽度
Public-key cryptography
Modular exponentiation
Modular multiplication
Window length
