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

Re: [PrimeNumbers] Re: NewPGen Sieve Algorithm ?

Expand Messages
  • Jens Kruse Andersen
    ... You can Google Baby Step Giant Step. It s an algorithm for discrete logarithms. It s used for fixed k sieves , i.e forms like k*2^n+/-1 where k is fixed
    Message 1 of 8 , Jan 8, 2013
    • 0 Attachment
      Mohsen wrote:
      > I have read somewhere that NewPGen uses BSBG (Baby Step Giant Step)!
      > Anybody knows? Although NewPGen is a native app vs Mathematica as
      > being managed and under JVM overhead, but I should be able to sieve not
      > faster but at least equal to NewPGen. Please help me.

      You can Google Baby Step Giant Step. It's an algorithm for discrete
      logarithms. It's used for "fixed k sieves", i.e forms like k*2^n+/-1 where
      k is fixed and n varies. This is very different from arithmetic progressions
      like k*n#+/-1 where n is fixed and k varies.

      You have unrealistic expectations about the efficiency of Mathematica.
      It has a lot of functions and makes it easy to program many problems
      but it's not particularly fast, at least not for the operations needed to
      search primes.
      The 5000 largest known primes at http://primes.utm.edu/primes/ were
      found with a variety of sieves, prp testers and primality provers, but
      I haven't heard of anyone who used Mathematica for any of the steps.

      --
      Jens Kruse Andersen
    Your message has been successfully submitted and would be delivered to recipients shortly.