Naslov
Evolutionary Algorithms for Finding Short Addition Chains: Going the Distance

Autori
Picek, Stjepan ; Coello Coello, Carlos A. ; Jakobovic, Domagoj ; Mentens, Nele

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
EvoCOP 2016 / - , 2016, 121-137

Skup
EvoCOP 2016

Mjesto i datum
Porto, Portugal, 30.03.2016. - 01.04.2016

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
Addition chains ; Cryptography ; Genetic algorithms ; Exponentiation

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA