FOM: AKS primality algorithm makes NYT
vznuri at earthlink.net
Fri Aug 9 02:29:12 EDT 2002
you have to register for NYT, but after you do,
you can read this article covering the world class algorithmic
breakthrough. saxena and kayal worked under agrawal as their advisor
advancing the result out of their **senior undergraduate thesis**
completed last may.
one wonders what other kind of amazing rabbits these
brilliant gentlemen could pull out of their hat in the times ahead!!
and maybe this story will bounce around the media some more, possibly
making the authors into semicelebrities (how famous can you get,
doing math, anyway?).
apparently the college they are at in india is one of the most
brutally selective and elite in the world. according to
one post on slashdot,
>Computer Science at IIT, Kanpur, incidentally, has traditionally been
>the most difficult course to gain admission into in the IIT system.
>About 250,000 applicants write a grueling entrance test (the JEE) to
>get admission to about 30~40 seats in CS/IITK.
here is the KS thesis online!! cited in the AKS paper.
oh (sheepish grin), I see it handles the relationship
to FLT and carmichael numbers and other standard primality tests
such as miller rabin & solvay strassen.
I suppose that this might be combined with the other paper
in future complete presentations of the algorithm written
up in books & elsewhere.
it looks like they used empirical testing of some of the
number theory conjectures in this paper. I would suggest that
number theory could experience a renaissance due to the new
strategy of fusion of theoretical and experimental (computational)
approaches (resisted by some .. perhaps at their peril!!).
one could speculate that maybe these author's breakthrough is partly
the result of their own mastery of it.
still no news on how the algorithm compares to miller
rabin (standard now used in cryptography)
in practice/performance. I imagine that will be an interesting
paper by somebody, fairly soon.
also I noticed in the above paper, it is all linked up to
the extended riemann hypothesis. so I am wondering if somehow
this algorithm & proof may shed new light on the riemann hypothesis????
which, by the way, has a ***$1,000,000*** prize on it from
clay math institute.
More information about the FOM