sidef-scripts/Math/lucas_V_pseudoprime_test.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 21 September 2023
# https://github.com/trizen

# High-level implementation of a simplified Baillie-PSW primality test with Lucas-V pseudoprimes.

# See also:
#   https://arxiv.org/pdf/2006.14425.pdf -- STRENGTHENING THE BAILLIE-PSW PRIMALITY TEST

# Find Q for P = 1, such that kronecker(1 - 4Q, n) = -1.
func findQ(N) {
    for k in (2 .. Inf) {

        var D = ((-1)**k * (2*k + 1))
        var K = kronecker(D, N)

        if (K.is_zero && gcd(D, N).is_between(2, N-1)) {
            return nil
        }

        return ((1 - D)/4) if (K == -1)
    }
}

func is_lucas_V_pseudoprime(n) {

    return false if (n <= 1)
    return true  if (n == 2)

    return false if n.is_even
    return false if n.is_power

    var P = 1
    var Q = findQ(n) \\ return false

    if (Q == -1) {
        P = 5
        Q = 5
    }

    lucasVmod(P, Q, n+1, n).is_congruent(2*Q, n)
}

func lucas_V_Baillie_PSW (n) {
    n.is_strong_pseudoprime(2) && is_lucas_V_pseudoprime(n)
}

var strong_lucas_psp       = [5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, 58519, 75077, 97439, 100127, 113573, 115639, 130139, 155819, 158399, 161027, 162133, 176399, 176471, 189419, 192509, 197801, 224369, 230691, 231703, 243629, 253259, 268349, 288919, 313499, 324899]
var extra_strong_lucas_psp = [989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, 72389, 73919, 75077, 100127, 113573, 125249, 137549, 137801, 153931, 155819, 161027, 162133, 189419, 218321, 231703, 249331, 370229, 429479, 430127, 459191, 473891, 480689, 600059, 621781, 632249, 635627]

say 25.by(lucas_V_Baillie_PSW)

assert_eq(strong_lucas_psp.grep(is_lucas_V_pseudoprime), [])
assert_eq(extra_strong_lucas_psp.grep(is_lucas_V_pseudoprime), [])

assert([913, 150267335403, 430558874533, 14760229232131, 936916995253453].all(is_lucas_V_pseudoprime))