FOM: P time primality proof vznuri at
Wed Aug 7 14:04:11 EDT 2002

here's manindra agrawals CV, principal author of the
P time primality proof. news of which was even carried
on slashdot yesterday, which as I understand has about
a quarter million readers. he's
collaborated with allender & rudich, both premiere
in the complexity theory field. his refs go back only
about 3 years. which suggests hes relatively new to
complexity theory & if correct has pulled off a 
striking coup.

personally, reacting superficially to the proof,
I think it would benefit by saying something
about the relationship to fermat's little theorem
testing, & maybe also throw in a reference to shor's
quantum algorithm as a key signpost for future directions in
the area.  my first reaction was that it was
a variation of FLT, if the authors immediately handle that objection
it might go down smoother.

if the algorithm works, one would speculate, depending
on performance, it would be used in cryptographic applications 
that verify primality, possibly replacing the standard miller-rabin test.
a key question will be how the two compare empirically for
the large prime numbers tested. if miller-rabin were significantly
faster even at a high certainty rate for large primes.. the
agrawal test might not be used by implementers.
(similar to the outcome of the linear programming P time algorithm)

More information about the FOM mailing list