TU Darmstadt / ULB / TUbiblio

Parallel algorithms for modular multi-exponentiation

Borges, Fábio ; Lara, Pedro ; Portugal, Renato :
Parallel algorithms for modular multi-exponentiation.
In: Applied Mathematics and Computation, 292 406--416.
[Artikel] , (2017)

Kurzbeschreibung (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.

Typ des Eintrags: Artikel
Erschienen: 2017
Autor(en): Borges, Fábio ; Lara, Pedro ; Portugal, Renato
Titel: Parallel algorithms for modular multi-exponentiation
Sprache: Deutsch
Kurzbeschreibung (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.

Titel der Zeitschrift, Zeitung oder Schriftenreihe: Applied Mathematics and Computation
Band: 292
Freie Schlagworte: - SST: CASED:
Fachbereich(e)/-gebiet(e): LOEWE > LOEWE-Zentren > CASED – Center for Advanced Security Research Darmstadt
20 Fachbereich Informatik > Telekooperation
LOEWE > LOEWE-Zentren
20 Fachbereich Informatik
LOEWE
Hinterlegungsdatum: 31 Dez 2016 12:59
DOI: 10.1016/j.amc.2016.07.036
ID-Nummer: TUD-CS-2017-0002
Export:

Optionen (nur für Redakteure)

Eintrag anzeigen Eintrag anzeigen