| 1234567891011121314151617181920212223242526272829303132333435363738394041 |
- #!/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 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 q = Quadratic(1, 1, c)
- q.powmod(n,n) == q.conj.mod(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]
|
