The Division Barrier: Optimal Bounds and Structural Limits in Toom-Cook Interpolation

Toom-Cook-$k$ ($2 \le k \in \mathbb{N}$) is a family of fast algorithms for multiplying long integers using $O\left(n^{\log_k(2k-1)}\right)$ arithmetic operations, offering asymptotical improvement over the naïve quadratic-time schoolbook approach. Despite this advantage, Toom-Cook algorithms often involve nontrivial divisions, divisions by elements that are not powers of $2$, which can be both computationally expensive and numerically unstable, especially in cryptography or quantum computing applications. Reducing or eliminating these divisions is therefore of significant theoretical and practical interest.