How to compute modular exponentiation with large operators based on the right-to-left binary algorithm

摘要

When the lengths of the operators are at least 1024 binary or 300 decimal digits, modular exponentiation can be time-consuming and is often the dominant part of the computation in many computer algebra systems. The prime approach on this computational problem is known as the square-and-multiply method, which includes two versions, i.e. the left-to-right binary algorithm and the right-to-left binary algorithm. For the past years, too many attentions have been paid to propose the fast modular exponentiation methods based on the left-to-right binary algorithm. However, extremely few attentions have been paid on developing the fast modular exponentiation methods based on the right-to-left binary algorithm. In this paper, we propose a t-fold exponent method based on the right-to-left binary algorithm. From the performance view, our t-fold exponent method is similar to the m-ary method based on the left-to-right binary algorithm. From the structure view, our t-fold exponent method offers a framework for the fast modular exponentiation methods based on the right-to-left binary algorithm. More important, it is the first but steady step to develop the fast modular exponentiation methods based on the right-to-left binary algorithm.