Paper Info
Title
Parallel algorithms for modular multi-exponentiation.
Abstract
Modular exponentiation is a time-consuming operation widely used in cryptography. Modular multi-exponentiation, a generalization of modular exponentiation also used in cryptography, deserves further analysis from the algorithmic point of view. The parallelization of modular multi-exponentiation can be obtained by generalizing methods used to parallelize modular exponentiation. In this paper, we present a new parallelization method for the modular multi-exponentiation operation with two optimizations. The first one searches for the fastest solution without taking into account the number of processors. The second one balances the load among the processors and finds the smallest number of processors that achieves the fastest solution. In detail, our algorithms compute the product of i modular exponentiations. They split up each exponent in j blocks and start j threads. Each thread processes together i blocks from different exponents. Thus, each block of an exponent is processed in a different thread, but the blocks of different exponents are processed together in the same thread. Using addition chains, we show the minimum number of threads with load balance and optimal running time. Therefore, the algorithms are optimized to run with the minimum time and the minimum number of processors.
Year
DOI
Venue
2017
10.1016/j.amc.2016.07.036
Applied Mathematics and Computation
Keywords
Field
DocType
Modular exponentiation,Modular multi-exponentiation,Parallelization,Algorithms,Cryptography
Load balancing (computing),Parallel algorithm,Computer science,Cryptography,Parallel computing,Thread (computing),Modular design,Exponentiation by squaring,Exponentiation,Modular exponentiation
Journal
Volume
Issue
ISSN
292
C
0096-3003
Citations 
PageRank 
References 
4
0.43
7
Authors
3
Name
Order
Citations
PageRank
Fábio Borges1254.13
Pedro C. Lara281.19
Renato Portugal35210.01