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