# What is the fastest algorithm for multiplying one given number with many others?

When multiplying two numbers with each other, which are $$n$$-bit numbers, there are several algorithms like the one of Karatsuba ($$O(n^{\log_2 3})$$) and a new one doing it even better (Harvey - Van der Hoeven) with a complexity of $$O(n \cdot \log n)$$, which is much better, of course.

My question is now, if we a given a number $$x$$ and $$m$$ numbers $$y_1, \ldots, y_m$$, is there a faster algorithm than $$O(m \cdot f(n))$$, where $$f(n)$$ is the complexity of the fastest multiplication algorithm for just two numbers?

• "and a new one"? which one? what is your unit of computation? what is $n$? Oct 31, 2023 at 11:55
• I assume the "new one" refers to the Harvey–Van der Hoeven algorithm. Oct 31, 2023 at 11:59
• I adapted the question accordingly. Many thanks for your input. Oct 31, 2023 at 12:28
• I don't know your exact algorithmic cost model, but this should be relevant. Oct 31, 2023 at 18:52
• David Harvey. Joris van der Hoeven. "Integer multiplication in time $O(n\log n)$." Ann. of Math. (2) 193 (2) 563 - 617, March 2021. doi.org/10.4007/annals.2021.193.2.4 projecteuclid.org/journals/annals-of-mathematics/volume-193/… Oct 31, 2023 at 22:53