Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MODULAR ARITHMETICINTEGER MULTIPLICATION:
Reports tagged with modular arithmeticinteger multiplication:
TR08-023 | 10th January 2008
Anindya De, Piyush Kurur, Chandan Saha, Ramprasad Saptharishi

Fast Integer Multiplication using Modular Arithmetic

We give an $O(N\cdot \log N\cdot 2^{O(\log^*N)})$ algorithm for
multiplying two $N$-bit integers that improves the $O(N\cdot \log N\cdot \log\log N)$ algorithm by
Sch\"{o}nhage-Strassen. Both these algorithms use modular
arithmetic. Recently, F\"{u}rer gave an $O(N\cdot \log N\cdot 2^{O(\log^*N)})$ algorithm which however uses arithmetic over
complex numbers as opposed to ... more >>>

ISSN 1433-8092 | Imprint