Fast integer multiplication using modular arithmetic

Anindya De*, Piyush Kurur, Chandan Sana, Ramprasad Saptharishi

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Scopus citations

Abstract

We give an O(N · log N ̇ 2O (log* N )algorithm for multiplying two N-bit integers that improves the O(N · log N · log log N) algorithm by Schönhage-Strassen |10|. Both these algorithms use modular arithmetic. Recently, Fürer |2| gave an O(N · log N ̇ 2O (log* 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 fron Fürer's algorithm to achieve this improvement in the modular setting. Our algorithm can also be viewed as a p-adic version of Fürer's algorithm. Thus, we show that the two seemingly different approaches to integer multiplication, modular and complex arithmetic, are similar.

Original languageEnglish (US)
Title of host publicationSTOC'08
Subtitle of host publicationProceedings of the 2008 ACM Symposium on Theory of Computing
Pages499-505
Number of pages7
StatePublished - Dec 8 2008
Event40th Annual ACM Symposium on Theory of Computing, STOC 2008 - Victoria, BC, Canada
Duration: May 17 2008May 20 2008

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other40th Annual ACM Symposium on Theory of Computing, STOC 2008
CountryCanada
CityVictoria, BC
Period5/17/085/20/08

Keywords

  • Computational algebra
  • Integer multiplication
  • Modular arithmetic

ASJC Scopus subject areas

  • Software

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

  • Cite this

    De, A., Kurur, P., Sana, C., & Saptharishi, R. (2008). Fast integer multiplication using modular arithmetic. In STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing (pp. 499-505). (Proceedings of the Annual ACM Symposium on Theory of Computing).