TY - GEN

T1 - Fast integer multiplication using modular arithmetic

AU - De, Anindya

AU - Kurur, Piyush

AU - Sana, Chandan

AU - Saptharishi, Ramprasad

PY - 2008/12/8

Y1 - 2008/12/8

N2 - 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.

AB - 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.

KW - Computational algebra

KW - Integer multiplication

KW - Modular arithmetic

UR - http://www.scopus.com/inward/record.url?scp=57049170396&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57049170396&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:57049170396

SN - 9781605580470

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 499

EP - 505

BT - STOC'08

T2 - 40th Annual ACM Symposium on Theory of Computing, STOC 2008

Y2 - 17 May 2008 through 20 May 2008

ER -