| 对一种快速双重指数模算法的复杂度研究 |
| |
| 引用本文： | 金海晻,许胤龙,王石.对一种快速双重指数模算法的复杂度研究[J].中国科学技术大学学报,2010,40(11). |
| |
| 作者姓名： | 金海晻 许胤龙 王石 |
| |
| 摘 要： | 最近提出了一种采用标准符号数二进制码(canonic signed-digit binary representation,CSDBR)来计算AXBY(modN)的快速双重指数模算法.该算法声明当指数的长度为k时,该算法平均仅需要1.306k次模乘.由于已知的此类算法至少需要1.503k次模乘,该算法具有明显的性能优势.然而,无论是该算法的提出者还是其他研究者均没有给出正确的复杂度分析.本文通过利用马尔科夫链模型对该算法进行正式的复杂度研究并进行一定规模的统计实验后证实,实际上该算法平均需要1.556k次模乘.这项研究的意义在于揭示到目前为止,基于标准符号数位码的双重指数模算法的最高性能仍然无法降低到1.5k次模乘以下.
|
| 关 键 词： | 双重指数模 模乘 标准符号数二进制码 马尔科夫链 海明距离 |
Complexity analysis of a fast modular multi-exponentiation algorithm |
| |
| JIN Haimin,XU Yinlong,Wong D S.Complexity analysis of a fast modular multi-exponentiation algorithm[J].Journal of University of Science and Technology of China,2010,40(11). |
| |
| Authors: | JIN Haimin XU Yinlong Wong D S |
| |
| Institution: | JIN Haimin,XU Yinlong,Wong D S2 |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
