Paperlane

no. 15 · Monday 16 November 2026

Long rational and Gaussian integer multiplication

Yuval Spiizer and Raphael S. Steiner

math.NT · via cs.DS · 38 pp

Abstract

Long integer multiplication is a fundamental operation in computational algebra, heavily relying on Toom–Cook and related evaluation-interpolation algorithms. Conventional wisdom dictates that multiplication on the Gaussian integers $\mathbb{Z}[i]$ is reduced to standard rational integer multiplication, since $\mathbb{Z}[i]$ is a ring extension of $\mathbb{Z}$. We show that this approach is far from optimal and moreover inverting this established paradigm, that is reducing rational to Gaussian multiplication, leads to faster rational integer multiplication algorithms. We introduce a novel Toom–Cook framework that reduces rational long integer multiplication to Gaussian integer multiplication, yielding a strictly more efficient computational pipeline. By taking advantage of the special properties of the rational integer domain inside the Gaussian integers, we achieve a more favourable algebraic structure that reduces the overall arithmetic cost in every metric. To validate this theoretical shift, we provide a complete implementation of our algorithm. Benchmarks demonstrate that our approach outperforms the highly optimised GNU Multiple Precision Arithmetic Library (GMP) by up to 29\%, bridging a fundamental theoretical insight with significant practical improvements in high-performance computer algebra.

comments
38 pages
fields
Number Theory
pdf ↗ page arXiv:2611.18028 ↗