Boost logo

Boost :

From: Geoff Leyland (gley001_at_[hidden])
Date: 2003-09-18 16:37:35

Last year I saw an article in New Scientist about a new method of
checking primes developed by two undergrads at the IIT in Kanpur,
India. I can't remember all the details, but it was quite a
breakthrough, and a quick google reveals that the American Institute of
Mathematics thinks it's ok, and gives the names of the researchers:

> Goldston's presentation on Friday, March 28, will come at a timely
> moment. Some of the world's leading mathematicians will be in Palo
> Alto for a brainstorming session on Algorithmic Number Theory. The
> conference, one of a series to be hosted by AIM over the next few
> years, was assembled to examine and possibly extend the recent
> breakthrough in primality testing announced last year by computer
> scientist Manindra Agrawal of the Indian Institute of Technology in
> Kanpur, and his students Neeraj Kayal and Nitin Saxena.

Papers with their names in turn up all over citeseer.

As I remember, the algorithm was presented in the new scientist
article, so it shouldn't be hard to find out how to do it.


On Friday, Sep 19, 2003, at 00:50 Pacific/Auckland, Stephen Nutt wrote:

> Is there a better algorithm for checking primes? I was looking into
> Fermat's little theorem, but I haven't worked out how to calculate
> 2^(p -1)
> modulus p where p can be any arbitrary 32 bit prime number candidate.
> I
> believe I can do it for p up to 65535 (which gives 2^p of 1e+19728),
> but
> I've gained nothing as my brute force method handle primes 12 bits
> larger.
> However, I'd be the first to admit that my math theory is poor, and
> mostly
> forgotten so it is possible I've overloked a better method.
> Stephen

Boost list run by bdawes at, gregod at, cpdaniel at, john at