New BPSW test option
tsurzin at comcast.net
Thu Apr 25 22:23:09 UTC 2019
Please make step 1 in the new BPSW test explicitly optional. If the
candidate prime is known to have no small factors then step 1 is
just wastes time. It is not likely to waste more than a few minutes
but there are many ways to avoid candidates with none of the first
few thousand primes as factors.
If the step oneis already a user’s option great. If not consider a
function parameter that lets the caller avoid it. It could even be an
optional parameter or some thing else.
I am looking forward to the new test. Thank you for the great work.
>From the Wikipedia: The test
Let /n/ be the odd positive integer that we wish to test for primality.
Optionally, perform trial division
<https://en.wikipedia.org/wiki/Trial_division> to check if /n/ is
divisible by a small prime number
<https://en.wikipedia.org/wiki/Prime_number> less than some
Perform a base 2 strong probable prime
<https://en.wikipedia.org/wiki/Strong_pseudoprime> test. If /n/ is
not a strong probable prime base 2, then /n/ is composite; quit.
Find the first /D/ in the sequence 5, −7, 9, −11, 13, −15, ... for
which the Jacobi symbol
<https://en.wikipedia.org/wiki/Jacobi_symbol> (/D///n/) is −1. Set
/P/ = 1 and /Q/ = (1 − /D/) / 4.
Perform a strong Lucas probable prime
test on /n/ using parameters /D/, /P/, and /Q/. If /n/ is not a
strong Lucas probable prime, then /n/ is composite. Otherwise, /n/
is almost certainly prime.
The first step is for efficiency only. The Baillie-PSW test works
without this step, but if /n/ has small prime factors, then the
quickest way to show that /n/ is composite is to find a factor by
More information about the gmp-discuss