Fast Integer Multiplication Using Modular Arithmetic

DOI10.1137/100811167zbMath1271.68247arXiv0801.1416OpenAlexW2018022095MaRDI QIDQ2840990

Anindya De, Ramprasad Saptharishi, Chandan Saha, Piyush P. Kurur

Publication date: 24 July 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0801.1416

zbMATH Keywords

fast Fourier transformmodular arithmeticinteger multiplication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Numerical methods for discrete and fast Fourier transforms (65T50)

Related Items (11)

Tighter Fourier Transform Lower Bounds ⋮ Even faster integer multiplication ⋮ Polynomial Multiplication over Finite Fields in Time \( O(n \log n \) ⋮ Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields ⋮ Integer multiplication in time \(O(n\log n)\) ⋮ Finding the subsets of variables of a partial Boolean function which are sufficient for its implementation in the classes defined by predicates ⋮ On a fast algorithm for computing the Fourier transform ⋮ Faster integer multiplication using short lattice vectors ⋮ On the complexity of inverting integer and polynomial matrices ⋮ Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth ⋮ Unnamed Item

This page was built for publication: Fast Integer Multiplication Using Modular Arithmetic