Parallel number multiplication algorithm

Abstract

Modulo multiplication, where the modulus is an n-digit number, with n approximately equal to 2⁹, 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.