Title:Fast Integer multiplication using modular arithmetic
Speaker: Piyush Kurur Indian Institute of Technology Kanpur
Time: 2009-06-12 10:00-2009-06-12 11:00
Venue:FIT Building 4-603, Tsinghua University
Download:Click!

Abstract:

In this talk I will present an n .log n . 2^{log^*{n}} algorithm to find the product of two integers which uses modular arithmetic instead of complex arithmetic. The algorithm is inspired from the recent breakthrough by Martin Fürer where he gave an algorithm with similar running time but uses complex arithmetic. Although we gain nothing in terms of running time, the use of modular arithmetic makes the algorithm simpler to understand and easier to prove correctness. However on the negative side the runtime bound depends on a deep theorem in analytic number theory on the density of primes in arithmetic progression originaly due to Linnik.

This is joint work with Anindya De, Chandan Saha and Ramprasad Saptarishi.



Short Bio:

Prof. Piyush Kurur was Ph.D from Institute of Mathematical Sciences Chennai, India. He is currently Assistant Professor, Department of Computer Science and Engg. IIT Kanpur. His research Interests mainly include Computational Algebra, Complexity and Quantum Computing.