## Re: sufficient test for primes with certificate

Expand Messages
• ... I should say that the program by Jen K. Andersen is a psp-sieve -- it generates a list of pseudoprimes for a given base and range, where gcd(base,n)==1.
Message 1 of 33 , May 16, 2012
--- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:

> Please see my draft paper at:
> http://www.mersenneforum.org/showpost.php?p=298027&postcount=44
> (Ignore the the mix up I made with the comparison between FFT multiplication and FFT squaring timings.)
>
> The 2.X selfridge composite test I have there has been tested to 4*10^12. I am planning to get to 10^14 in a core year, with the help of a prp-sieve written by Jens K. Anderson. I would go to 10^15 if my resources were not elsewhere employed.
>

I should say that the program by Jen K. Andersen is a "psp-sieve" -- it generates a list of pseudoprimes for a given base and range, where gcd(base,n)==1. For instance, I can pre-screen my test
(2+L)^(n+1)==5 (mod n, L^2+1) with output from Jens program for base 5:
5^(n+1)==25 (mod n).
This takes care of about half the throughput.

I then repeat the process for odd bases 7,...,29. This greatly reduces the amount of work my program has to do; It can then ignore the case where x<(31-5)/2 and gcd(base,n)==1

Paul
• ... I compiled a better version of my code with gmp 5.0.5, on a different box running at 3.6GHz and got some better timings { 17.505s pfgw (3-prp) 1m1.986s
Message 33 of 33 , Sep 21, 2012
--- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
:

> I ran various "minimal \lambda+2" tests on Gilbert Mozzo's 20,000 digit PRP, 5890*10^19996+2^66422-3 (x=1), using a 2.4GHz core:
> {
> 0m32.374s pfgw64 (3-prp)
> 1m9.876s pfgw64 -t
> 1m53.535s pfgw64 -tp
> 3m0.483s pfgw64 -tc
> 5m12.972s pfgw64 scriptify
> 4m4.811s gmp (-O3/no pgo)
> 4m9.148 pari-gp
> 1m15s theoretical Woltman implementation
> }
>

I compiled a better version of my code with gmp 5.0.5, on a different box running at 3.6GHz and got some better timings
{
17.505s pfgw (3-prp)
1m1.986s pfgw -tp
1m13.789s gmp (-O3/no pgo)
}

Paul
Your message has been successfully submitted and would be delivered to recipients shortly.