对一种快速双重指数模算法的复杂度研究

最近提出了一种采用标准符号数二进制码(canonic signed-digit binary representation,CSDBR)来计算AXBY(modN)的快速双重指数模算法.该算法声明当指数的长度为k时,该算法平均仅需要1.306k次模乘.由于已知的此类算法至少需要1.503k次模乘,该算法具有明显的性能优势.然而,无论是该算法的提出者还是其他研究者均没有给出正确的复杂度分析.本文通过利用马尔科夫链模型对该算法进行正式的复杂度研究并进行一定规模的统计实验后证实,实际上该算法平均需要1.556k次模乘.这项研究的意义在于揭示到目前为止,基于标准符号数位码的双重指数模算法的最高性能仍然无法降低到1.5k次模乘以下.