TU Darmstadt / ULB / TUbiblio

Parallel algorithms for modular multi-exponentiation

Borges, Fábio and Lara, Pedro and Portugal, Renato (2017):
Parallel algorithms for modular multi-exponentiation.
292, In: Applied Mathematics and Computation, pp. 406--416, DOI: 10.1016/j.amc.2016.07.036,
[Article]

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.

Item Type: Article
Erschienen: 2017
Creators: Borges, Fábio and Lara, Pedro and Portugal, Renato
Title: Parallel algorithms for modular multi-exponentiation
Language: German
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.

Journal or Publication Title: Applied Mathematics and Computation
Volume: 292
Uncontrolled Keywords: - SST: CASED:
Divisions: LOEWE > LOEWE-Zentren > CASED – Center for Advanced Security Research Darmstadt
20 Department of Computer Science > Telecooperation
LOEWE > LOEWE-Zentren
20 Department of Computer Science
LOEWE
Date Deposited: 31 Dec 2016 12:59
DOI: 10.1016/j.amc.2016.07.036
Identification Number: TUD-CS-2017-0002
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)

View Item View Item