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: