Re: Lucas tests with Fermat tests for free
- --- In email@example.com,
Phil Carmody <thefatphil@...> wrote:
> One caveat with two-for-the-price-of-one deals is that theIndeed. The decoupled version of CP Algorithm 3.5.9,
> two bits you get back might not actually be independent of
> each other, so you'd not be getting full value for money.
> It applies to all the Grantham one too of course.
with Paul's preferred parameters, is
Lucas with parameters (P,Q) = (c,1);
Fermat with base d = 2*x+5, where x is the smallest
non-negative integer for which kronecker(x^2-4,N) = -1.
These are not chosen independently by Paul, since
c = (d^2 - 2*d + 9)/(4*d) mod N ... 
turns out to be the rather delicate condition for
Paul's "Lucas test with Fermat test for free".
It is hard to see why  might induce a
correlation between the probabilities for Lucas
pseudoprimality and Fermat pseudoprimality.
But Phil is correct in pointing out that we
cannot entirely discount that possibility.
When kronecker(5,N) = -1, Grantham suggests
using a Frobenius test for which the CP separation
gives c = 3, for Lucas, and d = 5, for Fermat,
while BPSW choose c = 3 and d = 2. We likewise
cannot discount the possibility of correlated
probabilities in such circumstance.
--- In firstname.lastname@example.org, "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)