Spaces:
Sleeping
Sleeping
| from itertools import permutations | |
| from sympy.external.ntheory import (bit_scan1, remove, bit_scan0, is_fermat_prp, | |
| is_euler_prp, is_strong_prp, gcdext, _lucas_sequence, | |
| is_fibonacci_prp, is_lucas_prp, is_selfridge_prp, | |
| is_strong_lucas_prp, is_strong_selfridge_prp, | |
| is_bpsw_prp, is_strong_bpsw_prp) | |
| from sympy.testing.pytest import raises | |
| def test_bit_scan1(): | |
| assert bit_scan1(0) is None | |
| assert bit_scan1(1) == 0 | |
| assert bit_scan1(-1) == 0 | |
| assert bit_scan1(2) == 1 | |
| assert bit_scan1(7) == 0 | |
| assert bit_scan1(-7) == 0 | |
| for i in range(100): | |
| assert bit_scan1(1 << i) == i | |
| assert bit_scan1((1 << i) * 31337) == i | |
| for i in range(500): | |
| n = (1 << 500) + (1 << i) | |
| assert bit_scan1(n) == i | |
| assert bit_scan1(1 << 1000001) == 1000001 | |
| assert bit_scan1((1 << 273956)*7**37) == 273956 | |
| # issue 12709 | |
| for i in range(1, 10): | |
| big = 1 << i | |
| assert bit_scan1(-big) == bit_scan1(big) | |
| def test_bit_scan0(): | |
| assert bit_scan0(-1) is None | |
| assert bit_scan0(0) == 0 | |
| assert bit_scan0(1) == 1 | |
| assert bit_scan0(-2) == 0 | |
| def test_remove(): | |
| raises(ValueError, lambda: remove(1, 1)) | |
| assert remove(0, 3) == (0, 0) | |
| for f in range(2, 10): | |
| for y in range(2, 1000): | |
| for z in [1, 17, 101, 1009]: | |
| assert remove(z*f**y, f) == (z, y) | |
| def test_gcdext(): | |
| assert gcdext(0, 0) == (0, 0, 0) | |
| assert gcdext(3, 0) == (3, 1, 0) | |
| assert gcdext(0, 4) == (4, 0, 1) | |
| for n in range(1, 10): | |
| assert gcdext(n, 1) == gcdext(-n, 1) == (1, 0, 1) | |
| assert gcdext(n, -1) == gcdext(-n, -1) == (1, 0, -1) | |
| assert gcdext(n, n) == gcdext(-n, n) == (n, 0, 1) | |
| assert gcdext(n, -n) == gcdext(-n, -n) == (n, 0, -1) | |
| for n in range(2, 10): | |
| assert gcdext(1, n) == gcdext(1, -n) == (1, 1, 0) | |
| assert gcdext(-1, n) == gcdext(-1, -n) == (1, -1, 0) | |
| for a, b in permutations([2**5, 3, 5, 7**2, 11], 2): | |
| g, x, y = gcdext(a, b) | |
| assert g == a*x + b*y == 1 | |
| def test_is_fermat_prp(): | |
| # invalid input | |
| raises(ValueError, lambda: is_fermat_prp(0, 10)) | |
| raises(ValueError, lambda: is_fermat_prp(5, 1)) | |
| # n = 1 | |
| assert not is_fermat_prp(1, 3) | |
| # n is prime | |
| assert is_fermat_prp(2, 4) | |
| assert is_fermat_prp(3, 2) | |
| assert is_fermat_prp(11, 3) | |
| assert is_fermat_prp(2**31-1, 5) | |
| # A001567 | |
| pseudorpime = [341, 561, 645, 1105, 1387, 1729, 1905, 2047, | |
| 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681] | |
| for n in pseudorpime: | |
| assert is_fermat_prp(n, 2) | |
| # A020136 | |
| pseudorpime = [15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, | |
| 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905] | |
| for n in pseudorpime: | |
| assert is_fermat_prp(n, 4) | |
| def test_is_euler_prp(): | |
| # invalid input | |
| raises(ValueError, lambda: is_euler_prp(0, 10)) | |
| raises(ValueError, lambda: is_euler_prp(5, 1)) | |
| # n = 1 | |
| assert not is_euler_prp(1, 3) | |
| # n is prime | |
| assert is_euler_prp(2, 4) | |
| assert is_euler_prp(3, 2) | |
| assert is_euler_prp(11, 3) | |
| assert is_euler_prp(2**31-1, 5) | |
| # A047713 | |
| pseudorpime = [561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, | |
| 4681, 6601, 8321, 8481, 10585, 12801, 15841] | |
| for n in pseudorpime: | |
| assert is_euler_prp(n, 2) | |
| # A048950 | |
| pseudorpime = [121, 703, 1729, 1891, 2821, 3281, 7381, 8401, | |
| 8911, 10585, 12403, 15457, 15841, 16531, 18721] | |
| for n in pseudorpime: | |
| assert is_euler_prp(n, 3) | |
| def test_is_strong_prp(): | |
| # invalid input | |
| raises(ValueError, lambda: is_strong_prp(0, 10)) | |
| raises(ValueError, lambda: is_strong_prp(5, 1)) | |
| # n = 1 | |
| assert not is_strong_prp(1, 3) | |
| # n is prime | |
| assert is_strong_prp(2, 4) | |
| assert is_strong_prp(3, 2) | |
| assert is_strong_prp(11, 3) | |
| assert is_strong_prp(2**31-1, 5) | |
| # A001262 | |
| pseudorpime = [2047, 3277, 4033, 4681, 8321, 15841, 29341, | |
| 42799, 49141, 52633, 65281, 74665, 80581] | |
| for n in pseudorpime: | |
| assert is_strong_prp(n, 2) | |
| # A020229 | |
| pseudorpime = [121, 703, 1891, 3281, 8401, 8911, 10585, 12403, | |
| 16531, 18721, 19345, 23521, 31621, 44287, 47197] | |
| for n in pseudorpime: | |
| assert is_strong_prp(n, 3) | |
| def test_lucas_sequence(): | |
| def lucas_u(P, Q, length): | |
| array = [0] * length | |
| array[1] = 1 | |
| for k in range(2, length): | |
| array[k] = P * array[k - 1] - Q * array[k - 2] | |
| return array | |
| def lucas_v(P, Q, length): | |
| array = [0] * length | |
| array[0] = 2 | |
| array[1] = P | |
| for k in range(2, length): | |
| array[k] = P * array[k - 1] - Q * array[k - 2] | |
| return array | |
| length = 20 | |
| for P in range(-10, 10): | |
| for Q in range(-10, 10): | |
| D = P**2 - 4*Q | |
| if D == 0: | |
| continue | |
| us = lucas_u(P, Q, length) | |
| vs = lucas_v(P, Q, length) | |
| for n in range(3, 100, 2): | |
| for k in range(length): | |
| U, V, Qk = _lucas_sequence(n, P, Q, k) | |
| assert U == us[k] % n | |
| assert V == vs[k] % n | |
| assert pow(Q, k, n) == Qk | |
| def test_is_fibonacci_prp(): | |
| # invalid input | |
| raises(ValueError, lambda: is_fibonacci_prp(3, 2, 1)) | |
| raises(ValueError, lambda: is_fibonacci_prp(3, -5, 1)) | |
| raises(ValueError, lambda: is_fibonacci_prp(3, 5, 2)) | |
| raises(ValueError, lambda: is_fibonacci_prp(0, 5, -1)) | |
| # n = 1 | |
| assert not is_fibonacci_prp(1, 3, 1) | |
| # n is prime | |
| assert is_fibonacci_prp(2, 5, 1) | |
| assert is_fibonacci_prp(3, 6, -1) | |
| assert is_fibonacci_prp(11, 7, 1) | |
| assert is_fibonacci_prp(2**31-1, 8, -1) | |
| # A005845 | |
| pseudorpime = [705, 2465, 2737, 3745, 4181, 5777, 6721, | |
| 10877, 13201, 15251, 24465, 29281, 34561] | |
| for n in pseudorpime: | |
| assert is_fibonacci_prp(n, 1, -1) | |
| def test_is_lucas_prp(): | |
| # invalid input | |
| raises(ValueError, lambda: is_lucas_prp(3, 2, 1)) | |
| raises(ValueError, lambda: is_lucas_prp(0, 5, -1)) | |
| raises(ValueError, lambda: is_lucas_prp(15, 3, 1)) | |
| # n = 1 | |
| assert not is_lucas_prp(1, 3, 1) | |
| # n is prime | |
| assert is_lucas_prp(2, 5, 2) | |
| assert is_lucas_prp(3, 6, -1) | |
| assert is_lucas_prp(11, 7, 5) | |
| assert is_lucas_prp(2**31-1, 8, -3) | |
| # A081264 | |
| pseudorpime = [323, 377, 1891, 3827, 4181, 5777, 6601, 6721, | |
| 8149, 10877, 11663, 13201, 13981, 15251, 17119] | |
| for n in pseudorpime: | |
| assert is_lucas_prp(n, 1, -1) | |
| def test_is_selfridge_prp(): | |
| # invalid input | |
| raises(ValueError, lambda: is_selfridge_prp(0)) | |
| # n = 1 | |
| assert not is_selfridge_prp(1) | |
| # n is prime | |
| assert is_selfridge_prp(2) | |
| assert is_selfridge_prp(3) | |
| assert is_selfridge_prp(11) | |
| assert is_selfridge_prp(2**31-1) | |
| # A217120 | |
| pseudorpime = [323, 377, 1159, 1829, 3827, 5459, 5777, 9071, | |
| 9179, 10877, 11419, 11663, 13919, 14839, 16109] | |
| for n in pseudorpime: | |
| assert is_selfridge_prp(n) | |
| def test_is_strong_lucas_prp(): | |
| # invalid input | |
| raises(ValueError, lambda: is_strong_lucas_prp(3, 2, 1)) | |
| raises(ValueError, lambda: is_strong_lucas_prp(0, 5, -1)) | |
| raises(ValueError, lambda: is_strong_lucas_prp(15, 3, 1)) | |
| # n = 1 | |
| assert not is_strong_lucas_prp(1, 3, 1) | |
| # n is prime | |
| assert is_strong_lucas_prp(2, 5, 2) | |
| assert is_strong_lucas_prp(3, 6, -1) | |
| assert is_strong_lucas_prp(11, 7, 5) | |
| assert is_strong_lucas_prp(2**31-1, 8, -3) | |
| def test_is_strong_selfridge_prp(): | |
| # invalid input | |
| raises(ValueError, lambda: is_strong_selfridge_prp(0)) | |
| # n = 1 | |
| assert not is_strong_selfridge_prp(1) | |
| # n is prime | |
| assert is_strong_selfridge_prp(2) | |
| assert is_strong_selfridge_prp(3) | |
| assert is_strong_selfridge_prp(11) | |
| assert is_strong_selfridge_prp(2**31-1) | |
| # A217255 | |
| pseudorpime = [5459, 5777, 10877, 16109, 18971, 22499, 24569, | |
| 25199, 40309, 58519, 75077, 97439, 100127, 113573] | |
| for n in pseudorpime: | |
| assert is_strong_selfridge_prp(n) | |
| def test_is_bpsw_prp(): | |
| # invalid input | |
| raises(ValueError, lambda: is_bpsw_prp(0)) | |
| # n = 1 | |
| assert not is_bpsw_prp(1) | |
| # n is prime | |
| assert is_bpsw_prp(2) | |
| assert is_bpsw_prp(3) | |
| assert is_bpsw_prp(11) | |
| assert is_bpsw_prp(2**31-1) | |
| def test_is_strong_bpsw_prp(): | |
| # invalid input | |
| raises(ValueError, lambda: is_strong_bpsw_prp(0)) | |
| # n = 1 | |
| assert not is_strong_bpsw_prp(1) | |
| # n is prime | |
| assert is_strong_bpsw_prp(2) | |
| assert is_strong_bpsw_prp(3) | |
| assert is_strong_bpsw_prp(11) | |
| assert is_strong_bpsw_prp(2**31-1) | |