Fast Integer Multiplication using Modular Arithmetic

Details Fast Integer Multiplication using Modular Arithmetic Fast Integer Multiplication using Modular Arithmetic

2008-01-09

arxiv.org/abs/0801.1416v3

Computer Science

Symbolic Computation

fixed some typos and references

Scientific paper

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 modular arithmetic. In this paper, we use multivariate polynomial multiplication along with ideas from F\"{u}rer's algorithm to achieve this improvement in the modular setting. Our algorithm can also be viewed as a $p$-adic version of F\"{u}rer's algorithm. Thus, we show that the two seemingly different approaches to integer multiplication, modular and complex arithmetic, are similar.

Affiliated with

Also associated with

No associations

Rating

Fast Integer Multiplication using Modular Arithmetic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast Integer Multiplication using Modular Arithmetic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Integer Multiplication using Modular Arithmetic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-670085