Borges, Fábio ; Lara, Pedro ; Portugal, Renato (2017)
Parallel algorithms for modular multi-exponentiation.
In: Applied Mathematics and Computation, 292
doi: 10.1016/j.amc.2016.07.036
Artikel, Bibliographie
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 |
| Art des Eintrags: | Bibliographie |
| Titel: | Parallel algorithms for modular multi-exponentiation |
| Sprache: | Deutsch |
| Publikationsjahr: | 2017 |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | Applied Mathematics and Computation |
| Jahrgang/Volume einer Zeitschrift: | 292 |
| DOI: | 10.1016/j.amc.2016.07.036 |
| 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. |
| Freie Schlagworte: | - SST: CASED: |
| ID-Nummer: | TUD-CS-2017-0002 |
| 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 |
| Letzte Änderung: | 17 Mai 2018 13:02 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum