Fast integer multiplication using modular arithmetic

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

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

We give an N · log N · 2O(log*N) time algorithm to multiply two N-bit integers that uses modular arithmetic for intermediate computations instead of arithmetic over complex numbers as in Fürer's algorithm, which also has the same and so far the best known complexity. The previous best algorithm using modular arithmetic (by Schönhage and Strassen) has complexity O(N · log N · log log N). The advantage of using modular arithmetic as opposed to complex number arithmetic is that we can completely evade the task of bounding the truncation error due to finite approximations of complex numbers, which makes the analysis relatively simple. Our algorithm is based upon Fürer's algorithm, but uses fast Fourier transform over multivariate polynomials along with an estimate of the least prime in an arithmetic progression to achieve this improvement in the modular setting. It can also be viewed as a p-adic version of Fürer's algorithm.

Original languageEnglish (US)
Pages (from-to)685-699
Number of pages15
JournalSIAM Journal on Computing
Volume42
Issue number2
DOIs
StatePublished - Jul 18 2013

Keywords

  • Fast Fourier transform
  • Integer multiplication
  • Modular arithmetic

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Fast integer multiplication using modular arithmetic'. Together they form a unique fingerprint.

Cite this