Re: [boost] Compile time prime numbers, powers and roots

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:

http://aimath.org/release_goldston.html

>  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.

http://citeseer.nj.nec.com/cs?submit=Documents&q=Agrawal-Saxena- 
Kayal+algorithm

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.

cheers,
goof

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