A Library for Parallel Modular Arithmetic
This paper describes a library of platform independent functions for performing modular arithmetic on a range of parallel hardware. It is based around an approximate Chinese remainder reconstruction which allows the most significant bits of the stored num
- PDF / 166,905 Bytes
- 8 Pages / 431 x 666 pts Page_size
- 26 Downloads / 206 Views
Abstract. This paper describes a library of platform independent functions for performing modular arithmetic on a range of parallel hardware. It is based around an approximate Chinese remainder reconstruction which allows the most significant bits of the stored number to be calculated without the cost of a full reconstruction. We describe how this can be used to calculate the length of a modular number, and also its applications to comparison and division.
1
Introduction
In a modular representation of integers an integer is stored as a list of residues to a list of co-prime moduli. This representation is well suited to parallel computing, and we shall discuss how the basic arithmetic operations can be performed on such a representation. To perform addition, subtraction or multiplication in a modular representation is a straightforward task, as the result can be calculated for each modulus independently. This results in a low parallel complexity, as no communication is needed. Tasks that are less straightforward are the calculation of number length (the number of moduli required to represent the number) and division with quotient and remainder. To enable these two tasks to be performed, two basic algorithms are used. These are an approximate Chinese remainder reconstruction and the reconstruction of a number to a small modulus (a previously unpublished result). Both of these methods enable information to be gathered which concerns the total number without the expense of a full reconstruction. We also outline a proposed library for modular arithmetic. This library is to follow the style of the Gnu Multiple Precision (GMP) library [7], in providing a platform independent set of functions. The library is to run on a variety of parallel platforms, including the MasPar MP-1, shared memory machines and clusters of workstations. It is hoped that the implementation of this library will provide both a contrast between competing algorithms, and a contrast between synchronous and asynchronous programming styles. P. Amestoy et al. (Eds.): Euro-Par’99, LNCS 1685, pp. 1476–1483, 1999. c Springer-Verlag Berlin Heidelberg 1999
A Library for Parallel Modular Arithmetic
2
1477
Modular Representation of Integers
In a modular representation a number is stored as a sequence of residues. Each residue corresponds to a different modulus, each of which is relatively prime to all of the others. If the moduli are p0 , p1 , . . . , pn−1 then an integer X would be represented as hx0 , x1 , . . . , xn−1 i where xi ≡ X(modpi ), 0 ≤ xi < pi . The product of all the moduli is M = p0 p1 . . . pn−1 . The Chinese Remainder Theorem (CRT) states that the system of simultaneous congruences, (1) X ≡ xi mod pi , 0 ≤ i < n − 1 has a unique solution mod p0 p1 . . . pn−1 , assuming gcd(pi , pj ) = 1, for i 6= j. We can obtain this unique solution using If Y ≡
n−1 X
M i yi
(mod M )
(2)
i=0
where Mi = M/pi and yi ≡ Mi−1 xi value of the residue class Y . 2.1
(mod pi ), then X is the least non-negative
An Approximate Chinese Remainder Reconstruc
Data Loading...
