Finding short and implementation-friendly addition chains with evolutionary algorithms
Finding the shortest addition chain for a given exponent is a significant problem in cryptography. In this work, we present a genetic algorithm with a novel encoding of solutions and new crossover and mutation operators to minimize the length of the addition chains corresponding to a given exponent....
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer-Verlag
2018
|
| Online Access: | http://hdl.handle.net/1721.1/115968 |
| _version_ | 1811092530627870720 |
|---|---|
| author | Coello, Carlos A C Jakobovic, Domagoj Mentens, Nele Coello, Carlos A. Coello Picek, Stjepan |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Coello, Carlos A C Jakobovic, Domagoj Mentens, Nele Coello, Carlos A. Coello Picek, Stjepan |
| author_sort | Coello, Carlos A C |
| collection | MIT |
| description | Finding the shortest addition chain for a given exponent is a significant problem in cryptography. In this work, we present a genetic algorithm with a novel encoding of solutions and new crossover and mutation operators to minimize the length of the addition chains corresponding to a given exponent. We also develop a repair strategy that significantly enhances the performance of our approach. The results are compared with respect to those generated by other metaheuristics for exponents of moderate size, but we also investigate values up to 2²⁵⁵ - 21. For numbers of such size, we were unable to find any results produced by other metaheuristics which could be used for comparison purposes. Therefore, we decided to add three additional strategies to serve as benchmarks. Our results indicate that the proposed approach is a very promising alternative to deal with this problem. We also consider a more practical perspective by taking into account the implementation cost of the chains: we optimize the addition chains with regards to the type of operations as well as the number of instructions required for the implementation. |
| first_indexed | 2024-09-23T15:19:41Z |
| format | Article |
| id | mit-1721.1/115968 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:19:41Z |
| publishDate | 2018 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/1159682022-10-02T02:13:57Z Finding short and implementation-friendly addition chains with evolutionary algorithms Coello, Carlos A C Jakobovic, Domagoj Mentens, Nele Coello, Carlos A. Coello Picek, Stjepan Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Picek, Stjepan Finding the shortest addition chain for a given exponent is a significant problem in cryptography. In this work, we present a genetic algorithm with a novel encoding of solutions and new crossover and mutation operators to minimize the length of the addition chains corresponding to a given exponent. We also develop a repair strategy that significantly enhances the performance of our approach. The results are compared with respect to those generated by other metaheuristics for exponents of moderate size, but we also investigate values up to 2²⁵⁵ - 21. For numbers of such size, we were unable to find any results produced by other metaheuristics which could be used for comparison purposes. Therefore, we decided to add three additional strategies to serve as benchmarks. Our results indicate that the proposed approach is a very promising alternative to deal with this problem. We also consider a more practical perspective by taking into account the implementation cost of the chains: we optimize the addition chains with regards to the type of operations as well as the number of instructions required for the implementation. 2018-05-30T15:43:44Z 2018-05-30T15:43:44Z 2017-06 2017-05 2018-05-20T03:43:11Z Article http://purl.org/eprint/type/JournalArticle 1381-1231 1572-9397 http://hdl.handle.net/1721.1/115968 Picek, Stjepan et al. “Finding Short and Implementation-Friendly Addition Chains with Evolutionary Algorithms.” Journal of Heuristics 24, 3 (June 2017): 457–481 © 2017 Springer Science+Business Media, LLC en https://doi.org/10.1007/s10732-017-9340-2 Journal of Heuristics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer Science+Business Media, LLC application/pdf Springer-Verlag Springer US |
| spellingShingle | Coello, Carlos A C Jakobovic, Domagoj Mentens, Nele Coello, Carlos A. Coello Picek, Stjepan Finding short and implementation-friendly addition chains with evolutionary algorithms |
| title | Finding short and implementation-friendly addition chains with evolutionary algorithms |
| title_full | Finding short and implementation-friendly addition chains with evolutionary algorithms |
| title_fullStr | Finding short and implementation-friendly addition chains with evolutionary algorithms |
| title_full_unstemmed | Finding short and implementation-friendly addition chains with evolutionary algorithms |
| title_short | Finding short and implementation-friendly addition chains with evolutionary algorithms |
| title_sort | finding short and implementation friendly addition chains with evolutionary algorithms |
| url | http://hdl.handle.net/1721.1/115968 |
| work_keys_str_mv | AT coellocarlosac findingshortandimplementationfriendlyadditionchainswithevolutionaryalgorithms AT jakobovicdomagoj findingshortandimplementationfriendlyadditionchainswithevolutionaryalgorithms AT mentensnele findingshortandimplementationfriendlyadditionchainswithevolutionaryalgorithms AT coellocarlosacoello findingshortandimplementationfriendlyadditionchainswithevolutionaryalgorithms AT picekstjepan findingshortandimplementationfriendlyadditionchainswithevolutionaryalgorithms |