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

Re: [PrimeNumbers] Primes in P?

Expand Messages
  • 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 1 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.