## Comparison of spsp to multiple bases, BPSW and Frobenius with method B*

Expand Messages
• 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
Message 1 of 2 , Jan 21, 2011
• 0 Attachment
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
• ... Then you re doing something wrong, or your library is optimised for one primitive (modular exponentiation), and horrifically slow for another (lucas
Message 2 of 2 , Feb 2, 2011
• 0 Attachment
--- On Fri, 1/21/11, Brian <btball@...> wrote:
> 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

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?

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.)

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