1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859 |
- #!/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))
|