Campus Event Calendar
Event Entry
What and Who
Fast Integer multiplication using modular arithmetic
Piyush Kurur
Indian Institute of Technology, Kanpur
Talk
Piyush is visitor of AG1 until July, 17th.
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 22 June 2009
13:00
30 Minutes
E1 4
024
Saarbrücken
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.
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.
Contact
Daniel Johannsen
--email hidden
passcode not visible
logged in users only
Daniel Johannsen, 06/18/2009 18:44 -- Created document.