SMART: Next talk by Jaikumar Radhakrishnan [The Primality Testing Algorithm of Agrawal, Kayal and Saxena]
Vishwas Patil
Saxena
Speaker : Jaikumar Radhakrishnan,
Toyota Technological Institute at Chicago
and
Tata Institute of Fundamental Research, Mumbai
Date : July 03, 2006 (Monday)
Venue & Time : Aula Alfa, Via Salaria 113, 3:00PM
Abstract : Primality testing has been a topic of study in
computer science for decades and many deep and
beautiful algorithms have been developed to this
problem. Prime numbers also have important practical
applications in cyrptographic protocols. In this
lecture, we will discuss the remarkable
deterministic polynomial-time primality testing
algorithm of Agrawal, Kayal and Saxena (2002), which
is a milestone in the centuries old quest for
understanding prime numbers. Here is what Carl
Friedrich Gauss, wrote in his Disquisitiones
Arithmeticae, 1801:
The problem of distinguishing prime numbers
from composite numbers and of resolving the
latter into their prime factors is known to be
one of the most important and useful in
arithmetic. It has engaged the industry and
wisdom of ancient and modern geometers to such
an extent that it would be superfluous to
discuss the problem at length... Further, the
dignity of the science itself seems to require
that every possible means be explored for the
solution of a problem so elegant and so
celebrated.
[This quote appeared in the original version of the
paper of Agrawal, Kayal and Saxena (2002).]
The lecture will be in two parts, each one hour
long. In the first, we will describe the
background and develop the algorithm. In the
second, we will present the proof of correctness.
The material should be accessible to most students
of computer science. Most of the discussion will
involve arithmetic modulo some primes and
polynomials. We will not assume any advance
knowledge of algebra or number theory.
The original papers appears in:
Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in P, Annals
of Mathematics 160 (2004), no. 2, pp. 781--793.
Our discussion in the second lecture will be based on the write-up:
Jaikumar Radhakrishnan, Kavitha Telikepalli and V Vinay,
News from India: PRIMES is in P, available at
http://www.tcs.tifr.res.in/~jaikumar/Papers/AKS-revised.pdf
http://www.dsi.uniroma1.it/smart
Please feel free to extend this invitation to other interested people.
--
with best regards from,
_____________________________________________________________________
Vishwas Patil
Dipartimento di Informatica
Universita degli Studi di Roma - La Sapienza
Via Salaria 113, 00198 Roma, Italy
Tel: +39-3341 02 8875 Fax: +39-06 8541 842
http://www.dsi.uniroma1.it/~patil ivis...@gmail.com
_____________________________________________________________________
Opportunity is missed by most because it is dressed in overalls
and looks like work. -- Thomas Edison
Vishwas Patil
http://www.dsi.uniroma1.it/smart
Prediction is very difficult, especially if it's about the
future. - Niels Bhor