quadratic_frobenius_primality_test_explicit.sf

#!/usr/bin/ruby

# A simple implemenetation of the Frobenius Quadratic pseudoprimality test.

# Conditions:
#   1. Make sure n is odd and is not a perfect power.
#   2. Find the smallest odd prime p such that kronecker(p, n) = -1.
#   3. Check if (1 + sqrt(p))^n == (1 - sqrt(p)) mod n.

# Generalized test:
#   1. Make sure n is odd and is not a perfect power.
#   2. Find the smallest squarefree number c such that kronecker(c, n) = -1.
#   3. Check if (a + b*sqrt(c))^n == (a - b*sqrt(c)) mod n, where a,b,c are all coprime with n.

# No counter-examples are known to this test.

func quadratic_powmod(x_a, x_b, w, n, m) {

    var c_x = 1
    var c_y = 0

    do {
        (c_x,c_y) = ((c_x*x_a + c_y*x_b*w)%m, (c_x*x_b + c_y*x_a)%m) if n.is_odd
        (x_a,x_b) = ((x_a*x_a + x_b*x_b*w)%m, (x_a*x_b + x_b*x_a)%m)
    } while (n >>= 1)

    (c_x, c_y)
}

func is_frobenius_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 c = (3..Inf -> lazy.grep { .is_prime }.first {|p|
        var k = kronecker(p, n)
        return false if ((k == 0) && (p != n))
        k == -1
    })

    var (x_a, x_b, w) = (1, 1, c)
    var (c_x, c_y) = quadratic_powmod(x_a, x_b, w, n, n)

    c_x.is_congruent(x_a, n) && c_y.is_congruent(-x_b, n)
}

var FPP_list = 100.by(is_frobenius_pseudoprime)
say FPP_list

assert_eq(FPP_list, 100.nprimes)

__END__
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541]