2011 | OriginalPaper | Buchkapitel
A Simulated Annealing Algorithm for the Problem of Minimal Addition Chains
verfasst von : Adan Jose-Garcia, Hillel Romero-Monsivais, Cindy G. Hernandez-Morales, Arturo Rodriguez-Cristerna, Ivan Rivera-Islas, Jose Torres-Jimenez
Erschienen in: Progress in Artificial Intelligence
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Cryptosystems require the computation of modular exponentiation, this operation is related to the problem of finding a minimal addition chain. However, obtaining the shortest addition chain of length
n
is an NP-Complete problem whose search space size is proportional to
n
!. This paper introduces a novel idea to compute the minimal addition chain problem, through an implementation of a Simulated Annealing (SA) algorithm. The representation used in our SA is based on Factorial Number System (FNS). We use a fine-tuning process to get the best performance of SA using a Covering Array (CA), Diophantine Equation solutions (DE) and Neighborhood Functions (NF). We present a parallel implementation to execute the fine-tuning process using a Message Passing Interface (MPI) and the Single Program Multiple Data (SPMD) model. These features, allowed us to calculate minimal addition chains for benchmarks considered difficult in very short time, the experimental results show that this approach is a viable alternative to solve the solution of the minimal addition chain problem.