New BPSW test option

[tsurzin]

    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.