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

Primes in P?

Expand Messages
  • Jane Jones
    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
    Message 1 of 4 , Aug 31, 2002
    • 0 Attachment
      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]
    • 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 2 of 4 , Sep 1 1:28 AM
      • 0 Attachment
        --- 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 3 of 4 , Sep 1 1:59 AM
        • 0 Attachment
          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 4 of 4 , Sep 1 10:48 AM
          • 0 Attachment
            > 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.