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

```