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.