BPSW Variation

Paul Underwood paulunderwood at mindless.com
Wed Apr 24 11:27:14 UTC 2019

I am happy to see in this thread, https://gmplib.org/list-archives/gmp-discuss/2019-April/006311.html, that:

"The next version will use BPSW
https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test for
primality testing (or more strictly compositeness testing)."

Will it be a strong 2-PRP test followed by a Lucas test on x^2-a*x+1: minimal a has Jacobi(a^2-4,n) == -1?

Are you aware of my variation which runs quicker, albeit for single tests:

For non-square odd N find minimal a>2 such that JacobiSymbol(a^2-4,N)==-1
and perform the probable prime test:
(2*x)^((N+1)/2)==JacobiSymbol(2*(a+2),N)*2 mod(N, x^2-a*x+1)
Verified for N < 2^64 ?

The speed of this relies on the square of the intermediate values, s*x+t, in left-right exponentiation, is:



More information about the gmp-discuss mailing list