Efficient Pre-processing for Large Window-Based Modular Exponentiation Using Genetic Algorithms

摘要

Modular exponentiation is a cornerstone operation to several public-key cryptosystems. It is performed using successive modular multiplications. This operation is time consuming for large operands, which is always the case in cryptography. For software or hardware fast cryptosystems, one needs thus reducing the total number of modular multiplication required. Existing methods attempt to reduce this number by partitioning the exponent in constant or variable size windows. However, these window methods require some pre-computations, which themselves consist of modular exponentiations. In this paper, we exploit genetic algorithms to evolving an optimal addition sequence that allows one to perform the pre-computations in window methods with a minimal number of modular multiplications. Hence we improve the efficiency of modular exponentiation. We compare the evolved addition sequences with those obtained using Brun's algorithm.