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?
