Name
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. Both these algorithms use modular arithmetic. Recently, Fürer 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 from 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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1374376.1374447 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | DocType | Volume |
log log n,n-bit integer,complex arithmetic,p-adic version,modular setting,complex number,computational algebra,different approach,modular arithmetic,multivariate polynomial multiplication,integer multiplication | Journal | abs/0801.1416 |
ISSN | Citations | PageRank |
0737-8017 | 14 | 0.90 |
References | Authors | |
5 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anindya De | 1 | 239 | 24.77 |
| Piyush P. Kurur | 2 | 88 | 9.41 |
| Chandan Saha | 3 | 227 | 16.91 |
| Ramprasad Saptharishi | 4 | 184 | 13.72 |