TY - JOUR
T1 - An artificial immune system heuristic for generating short addition chains
AU - Cruz-Cortés, Nareli
AU - Rodríguez-Henríquez, francisco
AU - Coello Coello, Carlos A.
N1 - Funding Information:
Manuscript received April 22, 2005; revised October 15, 2005 and January 9, 2006. The work of N. Cruz-Cortés was supported by Project SIP-IPN 20072170. The work of F. Rodríguez-Henríquez was supported in part by CONACyT under Project 45306-Y. The work of C.A. Coello Coello was supported in part by CONACyT under Project 45683-Y.
PY - 2008/2
Y1 - 2008/2
N2 - This paper deals with the optimal computation of finite field exponentiation, which is a well-studied problem with many important applications in the areas of error-correcting codes and cryptography. It has been shown that the optimal computation of finite field exponentiation is a problem which is closely related to finding a suitable addition chain with the shortest possible length. However, it is also known that obtaining the shortest addition chain for a given arbitrary exponent is an NP-hard problem. As a consequence, heuristics are an obvious choice to compute field exponentiation with a semi-optimal number of underlying arithmetic operations. In this paper, we propose the use of an artificial immune system to tackle this problem. Particularly, we study the problem of finding both the shortest addition chains for exponents e with moderate size (i.e., with a length of less than 20 bits), and for the huge exponents typically adopted in cryptographic applications, (i.e., in the range from 128 to 2048 bits).
AB - This paper deals with the optimal computation of finite field exponentiation, which is a well-studied problem with many important applications in the areas of error-correcting codes and cryptography. It has been shown that the optimal computation of finite field exponentiation is a problem which is closely related to finding a suitable addition chain with the shortest possible length. However, it is also known that obtaining the shortest addition chain for a given arbitrary exponent is an NP-hard problem. As a consequence, heuristics are an obvious choice to compute field exponentiation with a semi-optimal number of underlying arithmetic operations. In this paper, we propose the use of an artificial immune system to tackle this problem. Particularly, we study the problem of finding both the shortest addition chains for exponents e with moderate size (i.e., with a length of less than 20 bits), and for the huge exponents typically adopted in cryptographic applications, (i.e., in the range from 128 to 2048 bits).
KW - Artificial immune systems (AIS)
KW - Cryptography
KW - Heuristics
KW - Shortest addition chains
UR - http://www.scopus.com/inward/record.url?scp=40249090400&partnerID=8YFLogxK
U2 - 10.1109/TEVC.2007.906082
DO - 10.1109/TEVC.2007.906082
M3 - Artículo
SN - 1089-778X
VL - 12
SP - 1
EP - 24
JO - IEEE Transactions on Evolutionary Computation
JF - IEEE Transactions on Evolutionary Computation
IS - 1
ER -