Parallel number multiplication algorithm

М.А. Cherepniov


Modulo multiplication, where the modulus is an n-digit number, with n approximately equal to 29, is currently the main operation in the discrete logarithm algorithm. If we consider this process as multiplication of big numbers followed by taking modulo (division with remainder), then the latter is the most difficult. We suggest looking at this problem in a different way. Namely, in terms of minimizing time with an unlimited number of computing nodes. This also includes the problem of parallelization on a chip, where the nodes that perform calculations are numerous, but low-power, primarily in memory, and the connections between them are fast. We propose an algorithm for modulo multiplication taking with precalculations stored distributed. The same configuration will significantly reduce the time for multiplication with a fixed multiplier. For the multiplication itself, a parallelized column algorithm is used. The running time of the constructed algorithm on a distributed computing system is estimated by the value O (log n), and taking into account the conveyor calculation system is performed in one clock cycle.

Full Text:

PDF (Russian)


Karacuba A.A., Ofman Ju.P. Umnozhenie mnogoznachnyh chisel na avtomatah.// DAN SSSR, 1962, t.145(2), s.293-294

Aho A., Hopkroft Dzh., Ul'man Dzh. Postroenie i analiz vychislitel'nyh algoritmov. M.: MIR, 1979.

Vasilenko O.N. Teoretiko-chislovye algoritmy v kriptografii.// M., MCNMO, 2003, 328s.

Montgomery P.L. Modular multiplication without trial divizion.// Math. Comp., 1987, v.48(177), p.243-264

P.Giorgi, L.Imbert, T.Izard Paramodular multiplication on multi-core processors/ IEEE Symp. on Comp. Arithm. Apr. 2013, Austin TX, US 135-142 https://

R.P.Brent and P.Zimmermann Moder Computer Arithmetic.// Cambridg Univ. Press, 2010

K.Nitta, N.Katsuta, O.Matoba A method for Modulo Operation by use of Spatial parallelism.// LNCS v.5172(2008), p.98-103


  • There are currently no refbacks.

Abava  Absolutech Convergent 2020

ISSN: 2307-8162