Sliding Window Method by Using Different Bases

Te-Jen Chang, Chin-Lung Wu, I-Hui Pan, Heng-Long Lai and You-Ru Hong

ABSTRACT

  When the lengths of the operators are at least 1,024 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.
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. The well-known binary method computes mod N using an average number of 1.5k multiplications, where k is the number of bits in the binary expansion of E. In this paper, we use a different base b to compose the exponentiation E, where . We only need 2m-1multiplciations, where , to compute the exponentiation operations. We can pre-compute the products for , , , , so the used look-up table need (b-1) multiplications. If we use the signed-digit number for base b, i.e., , , , , 0, 1, 2, , , the size of the used look-up table can be only needed  multiplications. The computational complexity is also presented for modular exponentiation later.

KEYWORDS: Sliding window method; cryptography; signed-digit method; binary method, addition chain

Full Paper