New BPSW test option
tsurzin
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.
Ralph Peterson
>From the Wikipedia: The test
Let /n/ be the odd positive integer that we wish to test for primality.
1.
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
convenient limit.
2.
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.
3.
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.
4.
Perform a strong Lucas probable prime
<https://en.wikipedia.org/wiki/Lucas_pseudoprime#Strong_Lucas_pseudoprimes>
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.
Remarks.
1.
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
trial division.
More information about the gmp-discuss
mailing list