Loading ...
Sorry, an error occurred while loading the content.
 

Re: [PrimeNumbers] Primes in P?

Expand Messages
  • Phil Carmody
    ... Because nothing much has changed in the last week or so. ... Agrawal, Kayal, and Saxena, Bernstein, Lenstra, Morain. Are you counting modulo 5 or
    Message 1 of 4 , Sep 1, 2002
      --- Jane Jones <jane91108@...> wrote:
      > Hi all, and Phil, and Milton:
      >
      > I have not seen much news about the "new" algorithm for Primes in P, recently.

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

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

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

      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
    • djbroadhurst
      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
      Message 2 of 4 , Sep 1, 2002
        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
      • Yves Gallot
        ... 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
        Message 3 of 4 , Sep 1, 2002
          > 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
        Your message has been successfully submitted and would be delivered to recipients shortly.