- Hi all, and Phil, and Milton:

I have not seen much news about the "new" algorithm for Primes in P, recently.

Which way is the wind blowing? Now, lets try not to engage in name calling this time. Any new papers or ideas. (Only one person seems to have new ideas though).

Jane

---------------------------------

Do You Yahoo!?

Yahoo! Finance - Get real-time stock quotes

[Non-text portions of this message have been removed] - --- Jane Jones <jane91108@...> wrote:
> Hi all, and Phil, and Milton:

Because nothing much has changed in the last week or so.

>

> I have not seen much news about the "new" algorithm for Primes in P, recently.

> Which way is the wind blowing? Now, lets try not to engage in name calling this time. Any new

Agrawal, Kayal, and Saxena, Bernstein, Lenstra, Morain.

> papers or ideas. (Only one person seems to have new ideas though).

Are you counting modulo 5 or something?

Papers from 5, or should I say 0?, of the above are linked to from http://fatphil.org/maths/AKS/

The other new contributions are Yves Gallot's C++ implementations in 4

flavours of bignum/algebra implementation, Medhi Tibouchi's Pari/GP

implementation (without the perfect power test), and Allan K. Steel's

implementation in Magma (he's one of the Magma authors, and finds his

initials amusing in this context!)

Invitations are requested for

a) New implementations in new languages

b) An exposition of the Lenstra or Morain improvements

Phil

=====

"The hottest places in Hell are reserved for those who, in

times of moral crisis, preserved their neutrality."

-- John F. Kennedy, 24 June 1963, claiming to quote Dante,

to whom this has been incorrectly attributed ever since.

__________________________________________________

Do You Yahoo!?

Yahoo! Finance - Get real-time stock quotes

http://finance.yahoo.com - The most helpful piece of reporting that I have seen

on the AKS algorithm and its context is at

http://research.microsoft.com/~pleyland/primes/AKS.htm

Thanks Paul for those measured and courteous comments.

David > b) An exposition of the Lenstra or Morain improvements

I don't think that François Morain improved the algorithm. His paper just

indicates the proof of AKS theorem, the results of his implementation

and a comparison of performance with ECPP.

Bernstein explains Lenstra's improvement in his paper.

The conditions

n^(r-1)/q (mod r) != {0, 1}

and (q+s-1, s) >= n^{2 sqrt(r)}

can be replaced by

n is a primitive root modulo r

and (phi(r)+s-1, s) >= n^sqrt(r)

then we can use smaller values for r and s and it speeds up the algorithm.

Yves