Comparison of spsp to multiple bases, BPSW and Frobenius with method B*
- I've tested three approaches up to 2^64
1) Strong pseudo-prime test to multiple (up to nine) bases.
The bases I used are: 377687,1662803,61,2,7,13,23,3,5 and in that order, it seems to be a very efficient ordering at least for the numbers up to 2^64. Of course, this test isn't infinitely scalable but it does provide a fast deterministic test if the numbers are in this range.
2) BPSW test. Deterministic in this range. Not proven if there's a limit - no counter-examples known below 2^64
3) A Frobenius test with determinant selected according to method B* of the original paper by Wagstaff and Baillie, 1980
Deterministic in this range.
Timings on a XEON x5570 2.93 Ghz, 32GB ram:
First place = SPSP to multiple bases. The clear winner at 4481.6 seconds
Second place = Frobenius test at 20,070 seconds
Third place = BPSW at 22,506 seconds
Code written in Python using Nzmath libraries for the following functions: spsp, lpsp, fpsp, gcd, legendre (Jacobi test), issquare, and coprime
- --- On Fri, 1/21/11, Brian <btball@...> wrote:
> Timings on a XEON x5570 2.93 Ghz, 32GB ram:Then you're doing something wrong, or your library is optimised for one primitive (modular exponentiation), and horrifically slow for another (lucas sequence evaluation). What precisely was your input set?
> First place = SPSP to multiple bases. The clear winner at 4481.6 seconds
> Second place = Frobenius test at 20,070 seconds
> Third place = BPSW at 22,506 seconds
Are you comparing up-to-12th roots of unity in the multiple SPSP test? You ought to, that will make it a little quicker. (After the 2nd passed test there's a >50% chance that you'll have incompatible square roots of unity, and won't need to do a third test.)