New BPSW test option

tsurzin tsurzin at
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.


    Optionally, perform trial division
    <> to check if /n/ is
    divisible by a small prime number
    <> less than some
    convenient limit.


    Perform a base 2 strong probable prime
    <> 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
    <> (/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
    trial division.

More information about the gmp-discuss mailing list