Fast Integer multiplication using modular arithmetic

演讲人: Piyush Kurur Indian Institute of Technology Kanpur
时间: 2009-06-12 10:00-2009-06-12 11:00
地点:FIT Building 4-603, Tsinghua University

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.


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.