TY - JOUR
T1 - On the optimal computation of finite field exponentiation
AU - Cruz-Cortés, Nareli
AU - Rodríguez-Henríquez, Francisco
AU - Coello Coello, Carlos A.
PY - 2004
Y1 - 2004
N2 - It has been shown that the optimal computation of finite field exponentiation is closely related to the problem of finding a suitable addition chain with the shortest possible length. However, obtaining the shortest addition chain for a given arbitrary exponent is a NP-hard problem. Hence in general, we are forced to use some kind of heuristic in order to compute field exponentiation with a semi-optimal number of underlying arithmetic operations. In this paper we present a novel heuristic for that problem which is based on an immune artificial system strategy. The results obtained by our scheme yield the shortest reported lengths for the exponents typically used when computing field multiplicative inverses for error-correcting and elliptic curve cryptographic applications.
AB - It has been shown that the optimal computation of finite field exponentiation is closely related to the problem of finding a suitable addition chain with the shortest possible length. However, obtaining the shortest addition chain for a given arbitrary exponent is a NP-hard problem. Hence in general, we are forced to use some kind of heuristic in order to compute field exponentiation with a semi-optimal number of underlying arithmetic operations. In this paper we present a novel heuristic for that problem which is based on an immune artificial system strategy. The results obtained by our scheme yield the shortest reported lengths for the exponents typically used when computing field multiplicative inverses for error-correcting and elliptic curve cryptographic applications.
UR - http://www.scopus.com/inward/record.url?scp=22944458514&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-30498-2_75
DO - 10.1007/978-3-540-30498-2_75
M3 - Artículo de la conferencia
AN - SCOPUS:22944458514
SN - 0302-9743
VL - 3315
SP - 747
EP - 756
JO - Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)
JF - Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)
T2 - 9th Ibero-American Conference on AI: Advances in Artificial Intelligence- IBERAMIA 2004
Y2 - 22 November 2004 through 26 November 2004
ER -