模幂与点乘m_ary算法中窗口大小的最优化估计

On estimation of optimal window size in m_ary algorithm in modular exponentiation and point multiplication

提出一种新大数模幂与点乘m_ary算法中窗口大小的最优化估计方法。该方法不同于传统的暴力搜寻方法,也不同于在窗口的取值范围内通过逐一测试程序来获得最优窗口大小的方法。其基于以下理论分析:模幂m_ary算法的基本运算为大数乘法,其中包括大数平方算法和一般大数乘法;椭圆曲线加密算法中点乘的m_ary算法步骤与模幂的m_ary算法相同,后者的基本运算为倍乘和加法。根据m_ary算法的基本运算的调用次数,推算出了最优窗口大小的估计公式。通过实验对m_ary算法进行实现,并测试分析了根据估计公式计算出窗口大小的算法实现时间效率与理论分析基本吻合。

This paper proposed a new method for estimating optimal window size in m_ary algorithm in modular exponential and point multiplication. This method was different from traditional brute force search, and also different from the method that got the optimal window size by testing program one by one in window size range. The method this paper discussed was based following theoretic analysis ： Square and multiplication of large integer are two basic operations in modular exponential m_ary algorithm. The main operations of m_ary algorithm of point multiplication in elliptic curve encryption were doublings and point addition . The steps of m_ary algorithm in point multiplication was similar to modular exponential. According to the times of basic operation was called, calculated estimating formula of optimal window size. Besides, experimental results show that im- plementation efficiency of m_ary using window size calculated by estimating formula is corresponding to theoretic analysis.