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

Re: [PrimeNumbers] Primes in P?

Expand Messages
  • 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 1 of 4 , Sep 1, 2002
    • 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 2 of 4 , Sep 1, 2002
      • 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.