Fast Integer Muliplication Using Modular Arithmetic
Thursday 19 June 2008, 15.00, b-it 1.25 (cosec meeting room)
Chandan Saha ( Indian Institute of Technology, Kanpur)
We will discuss an adaptation of Fürer's (2007) algorithm for multiplying two N-bit integers. The algorithm uses arithmetic modulo prime powers (which we call modular arithmetic) as opposed to arithmetic over complex numbers in Fürer's algorithm. One advantage of using modular arithmetic is that, by choosing a prime carefully certain precision analysis associated with the algorithm can be made very simple. However, choosing an appropriate prime is a costly operation, which fortunately can be made easy by considering Fast Fourier Transform (FFT) over multivariate polynomials. All previous algorithms used FFT over univariate polynomials. Our algorithm can also be viewed as a p-adic version of Fürer's algorithm and achieves a running time of O(N.log N. 2^O(log* N)) bit operations.