# Largest parallelization speedup for multiplication of very large numbers

I have recently come across the following papers:

• S. Baktir and E. Savas. Highly-parallel Montgomery multiplication for multi-core general-purpose microprocessors. In E. Gelenbe and R. Lent, editors, Computer and Information Sciences III, pages 467–476. Springer London, 2013.
• P. Giorgi, L. Imbert, and T. Izard. Parallel modular multiplication on multi-core processors. In Computer Arithmetic (ARITH), 2013 21st IEEE Symposium on, pages 135–142, April 2013.
• B. S. Fagin, "Large integer multiplication on massively parallel processors," [1990 Proceedings] The Third Symposium on the Frontiers of Massively Parallel Computation, College Park, MD, 1990, pp. 38-42.

where they deal with the issue of computing a multiplication between large numbers (in the first two papers, up to approx $2^{14}$ bits, in the last one up to $2^{23}$ bits) using many processors simultaneously.

I was wondering: what happens beyond that? What is the theoretical maximum speedup for a $2^n$ bit multiplication, having an unlimited amount of processors at disposal? Can the wallclock time of the operation be made arbitrarily small? I guess there are communication bottlenecks among the processors?

• Please specify your model of computation. Because at some point physical limits and circuit limits (e.g. ignoring spacetime we live in a 3 dimensional world) and the speed of light limits come into play, if you want to be realistic. – orlp May 31 '17 at 23:31
• – D.W. Jun 1 '17 at 0:05