Sliding Window Method by Using Different Bases

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

《International Journal of Crisis Management》 2卷2期 (2012/07) Pp. 53-56

https://doi.org/10.6929/IJCM.201207_2(2).0003

摘要

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 CΞM^E 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 E=(e_m e_(m-1) … e_1)_b. We only need 2m-1multiplciations, where m=2k/b, to compute the exponentiation operations. We can pre-compute the products for M^1, M^2, …, M^(b-1) , so the used look-up table need (b-1) multiplications. If we use the signed-digit number for base b, i.e., -b/2-1,-b/2, -b/2+1, …, 0, 1, 2, …, b/2, the size of the used look-up table can be only needed b/2+1 multiplications. The computational complexity is also presented for modular exponentiation later.

關鍵字

Sliding window method ； cryptography ； signed-digit method ； binary method ； addition chain