Re: Lucas tests with Fermat tests for free
- --- In email@example.com, "djbroadhurst" <d.broadhurst@...> wrote:
>I need to amend this incarnation to 2 + 1 selfridge(s) for Grantham's RQFT as is clearly stated in C&P; The Lucas chain has to be computed first -- but surely Grantham's b^((n-1)/2) can be tested first, making it 1 + 2 selfridge?
> Paul Underwood's preprint at
> has a rather neat observation in Section 4, which is all one
> really needs to read to understand how Paul can do in
> 2 selfridges what takes BPSW 1 + 2 selfridges and takes
> Grantham 2 + 1 selfridges, using the Frobenius method of
> Crandall and Pomerance.
Thanks for your comments, David. Expect a extracted paper in due course.
My head is buried in the Lucas and Grantham's Frobenius tests sections of C&P and Jon's papers, along with your message.
--- 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)