TY - GEN
T1 - Finding optimal addition chains using a genetic algorithm approach
AU - Cruz-Cortés, Nareli
AU - Rodríguez-Henríquez, Francisco
AU - Juárez-Morales, Raúl
AU - Coello Coello, Carlos A.
PY - 2005
Y1 - 2005
N2 - Since most public key cryptosystem primitives require the computation of modular exponentiation as their main building block, the problem of performing modular exponentiation efficiently has received considerable attention over the years. It is known that optimal (shortest) addition chains are the key mathematical concept for accomplishing modular exponentiations optimally. However, finding an optimal addition chain of length r is an NP-hard problem whose search space size is comparable to r!. In this contribution we explore the usage of a Genetic Algorithm (GA) approach for the problem of finding optimal (shortest) addition chains. We explain our GA strategy in detail reporting several promising experimental results that suggest that evolutionary algorithms may be a viable alternative to solve this illustrious problem in a quasi optimal fashion.
AB - Since most public key cryptosystem primitives require the computation of modular exponentiation as their main building block, the problem of performing modular exponentiation efficiently has received considerable attention over the years. It is known that optimal (shortest) addition chains are the key mathematical concept for accomplishing modular exponentiations optimally. However, finding an optimal addition chain of length r is an NP-hard problem whose search space size is comparable to r!. In this contribution we explore the usage of a Genetic Algorithm (GA) approach for the problem of finding optimal (shortest) addition chains. We explain our GA strategy in detail reporting several promising experimental results that suggest that evolutionary algorithms may be a viable alternative to solve this illustrious problem in a quasi optimal fashion.
UR - http://www.scopus.com/inward/record.url?scp=33646844796&partnerID=8YFLogxK
U2 - 10.1007/11596448_30
DO - 10.1007/11596448_30
M3 - Contribución a la conferencia
SN - 3540308180
SN - 9783540308188
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 208
EP - 215
BT - Computational Intelligence and Security - International Conference, CIS 2005, Proceedings
PB - Springer Verlag
T2 - International Conference on Computational Intelligence and Security, CIS 2005
Y2 - 15 December 2005 through 19 December 2005
ER -