Evolutionary Algorithms for Finding Short Addition Chains: Going the Distance (CROSBI ID 633844)
Prilog sa skupa u zborniku | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Picek, Stjepan ; Coello Coello, Carlos A. ; Jakobovic, Domagoj ; Mentens, Nele
engleski
Evolutionary Algorithms for Finding Short Addition Chains: Going the Distance
The problem of finding the shortest addition chain for a given exponent is of great relevance in cryptography, but is also very difficult to solve since it is an NP-hard problem. In this paper, we propose a genetic algorithm with a novel representation 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 instances of moderate size, but we also investigate values up to 2^127−3. For those instances, we were unable to find any results produced by other metaheuristics for comparison, and three additional strategies were adopted in this case to serve as benchmarks. Our results indicate that the proposed approach is a very promising alternative to deal with this problem.
Addition chains ; Cryptography ; Genetic algorithms ; Exponentiation
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o prilogu
121-137.
2016.
objavljeno
Podaci o matičnoj publikaciji
EvoCOP 2016
Podaci o skupu
EvoCOP 2016
predavanje
30.03.2016-01.04.2016
Porto, Portugal