An artificial immune system heuristic for generating short addition chains

Nareli Cruz-Cortés, francisco Rodríguez-Henríquez, Carlos A. Coello Coello

Resultado de la investigación: Contribución a una revistaArtículo

24 Citas (Scopus)

Resumen

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). © 2007 IEEE.
Idioma originalInglés estadounidense
Páginas (desde-hasta)1-24
Número de páginas2
PublicaciónIEEE Transactions on Evolutionary Computation
DOI
EstadoPublicada - 1 feb 2008

Huella Profundice en los temas de investigación de 'An artificial immune system heuristic for generating short addition chains'. En conjunto forman una huella única.

  • Citar esto