Fast integer multiplication using modular arithmetic

DOI10.1137/100811167MaRDI QIDQ2840990zbMATH OpenOpenAlexFDO

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

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)

Abstract: We give an $O(NcdotlogNcdot{2}^{O(lo{g}^{\ast }N)})$ algorithm for multiplying two $N$-bit integers that improves the $O(NcdotlogNcdotloglogN)$ algorithm by Sch"{o}nhage-Strassen. Both these algorithms use modular arithmetic. Recently, F"{u}rer gave an $O(NcdotlogNcdot{2}^{O(lo{g}^{\ast }N)})$ algorithm which however uses arithmetic over complex numbers as opposed to modular arithmetic. In this paper, we use multivariate polynomial multiplication along with ideas from F"{u}rer's algorithm to achieve this improvement in the modular setting. Our algorithm can also be viewed as a $p$-adic version of F"{u}rer's algorithm. Thus, we show that the two seemingly different approaches to integer multiplication, modular and complex arithmetic, are similar.

Recommendations

• scientific article; zbMATH DE number 1294069
• A fast modular multiplication algorithm
• A faster modular multiplication algorithm
• Efficient Modular Arithmetic
• Topics in Cryptology – CT-RSA 2004
• Faster integer multiplication
• Faster integer multiplication
• Even faster integer multiplication
• Fast modular multiplication using 2-power radix
• scientific article; zbMATH DE number 4191561

Cited in

(29)

• Tighter Fourier transform lower bounds
• Finding the subsets of variables of a partial Boolean function which are sufficient for its implementation in the classes defined by predicates
• Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth
• Faster integer multiplication
• Efficient Modular Arithmetic
• Exploiting Linearity of Modular Multiplication
• On the complexity of inverting integer and polynomial matrices
• On a fast algorithm for computing the Fourier transform
• On Faster Integer Calculations Using Non-arithmetic Primitives
• Faster integer multiplication using short lattice vectors
• Fast on-line integer multiplication
• scientific article; zbMATH DE number 5679233 (Why is no real title available?)
• Fast on-line integer multiplication
• Even faster integer multiplication
• Integer multiplication in time \(O(n\log n)\)
• Multiple product modulo arbitrary numbers
• Multiple product modulo arbitrary numbers
• Topics in Cryptology – CT-RSA 2004
• Algorithmic counting of nonequivalent compact Huffman codes
• Polynomial multiplication over finite fields in time O(n n)
• Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
• scientific article; zbMATH DE number 3223196 (Why is no real title available?)
• Multiplication
• Another look at some fast modular arithmetic methods
• scientific article; zbMATH DE number 4104356 (Why is no real title available?)
• A rigorous extension of the Schönhage-Strassen integer multiplication algorithm using complex interval arithmetic
• Fast integer multiplication using generalized Fermat primes
• Modular SIMD arithmetic in \textsc{Mathemagix}
• Low-Weight Polynomial Form Integers for Efficient Modular Multiplication

This page was built for publication: Fast integer multiplication using modular arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2840990)