On Finding Short Addition Chains for Large Integers

The addition chain for a given exponent $n$ is an increasing sequence of positive integers: its first term is $1$, and each subsequent term is obtained by adding the previous two terms which can be the same , so that the last element of the sequence is equal to $n$. Constructing the shortest addition chain for a fixed exponent $n$ is the most efficient method for computing $x^n$ in some group under multiplication. Therefore, the addition chain plays a crucial role in modern cryptography. It can improve the computational efficiency of cryptographic algorithms that require fast exponentiation, such as RSA, ElGamal, Paillier, and ECC, etc. However, the problem of finding the shortest additive chain is textbf{NP}-Complete. Moreover, the existing evolutionary algorithms can not work well for finding short addition chains for large integers. This paper integrates genetic algorithms with the window method to obtain an efficient strategy for the addition chain problem involving large integers. We do experiments on an RSA-1536 modulus to verify the efficiency and practicability of our algorithm.