13832902924

Committed 13 Mar 2025 10:54AM CUT coverage: 99.579% (+0.001%) from 99.578%

Build # 13832902924

Build Type

Pull #359

github

Committed by

web-flow

Commit Message

Merge 658ddc81b into 3c5df06ae

Pull Request Pull Request #359: add release notes for 0.19.1 release

Run Details

2560 of 2571 branches covered (99.57%)

Branch coverage included in aggregate %.

6663 of 6691 relevant lines covered (99.58%)

19.18 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

99.52

/src/ecdsa/test_numbertheory.py

import operator
from functools import reduce
import sys

try:
    import unittest2 as unittest
except ImportError:
    import unittest
import hypothesis.strategies as st
import pytest
from hypothesis import given, settings, example

try:
    from hypothesis import HealthCheck

    HC_PRESENT = True
except ImportError:  # pragma: no cover
    HC_PRESENT = False
from .numbertheory import (
    SquareRootError,
    JacobiError,
    factorization,
    gcd,
    lcm,
    jacobi,
    inverse_mod,
    is_prime,
    next_prime,
    smallprimes,
    square_root_mod_prime,
)

try:
    from gmpy2 import mpz
except ImportError:
    try:
        from gmpy import mpz
    except ImportError:

        def mpz(x):
            return x


BIGPRIMES = (
    999671,
    999683,
    999721,
    999727,
    999749,
    999763,
    999769,
    999773,
    999809,
    999853,
    999863,
    999883,
    999907,
    999917,
    999931,
    999953,
    999959,
    999961,
    999979,
    999983,
)


@pytest.mark.parametrize(
    "prime, next_p", [(p, q) for p, q in zip(BIGPRIMES[:-1], BIGPRIMES[1:])]
)
def test_next_prime(prime, next_p):
    assert next_prime(prime) == next_p


@pytest.mark.parametrize("val", [-1, 0, 1])
def test_next_prime_with_nums_less_2(val):
    assert next_prime(val) == 2


@pytest.mark.slow
@pytest.mark.parametrize("prime", smallprimes)
def test_square_root_mod_prime_for_small_primes(prime):
    squares = set()
    for num in range(0, 1 + prime // 2):
        sq = num * num % prime
        squares.add(sq)
        root = square_root_mod_prime(sq, prime)
        # tested for real with TestNumbertheory.test_square_root_mod_prime
        assert root * root % prime == sq

    for nonsquare in range(0, prime):
        if nonsquare in squares:
            continue
        with pytest.raises(SquareRootError):
            square_root_mod_prime(nonsquare, prime)


def test_square_root_mod_prime_for_2():
    a = square_root_mod_prime(1, 2)
    assert a == 1


def test_square_root_mod_prime_for_small_prime():
    root = square_root_mod_prime(98**2 % 101, 101)
    assert root * root % 101 == 9


def test_square_root_mod_prime_for_p_congruent_5():
    p = 13
    assert p % 8 == 5

    root = square_root_mod_prime(3, p)
    assert root * root % p == 3


def test_square_root_mod_prime_for_p_congruent_5_large_d():
    p = 29
    assert p % 8 == 5

    root = square_root_mod_prime(4, p)
    assert root * root % p == 4


class TestSquareRootModPrime(unittest.TestCase):
    def test_power_of_2_p(self):
        with self.assertRaises(JacobiError):
            square_root_mod_prime(12, 32)

    def test_no_square(self):
        with self.assertRaises(SquareRootError) as e:
            square_root_mod_prime(12, 31)

        self.assertIn("no square root", str(e.exception))

    def test_non_prime(self):
        with self.assertRaises(SquareRootError) as e:
            square_root_mod_prime(12, 33)

        self.assertIn("p is not prime", str(e.exception))

    def test_non_prime_with_negative(self):
        with self.assertRaises(SquareRootError) as e:
            square_root_mod_prime(697 - 1, 697)

        self.assertIn("p is not prime", str(e.exception))


@st.composite
def st_two_nums_rel_prime(draw):
    # 521-bit is the biggest curve we operate on, use 1024 for a bit
    # of breathing space
    mod = draw(st.integers(min_value=2, max_value=2**1024))
    num = draw(
        st.integers(min_value=1, max_value=mod - 1).filter(
            lambda x: gcd(x, mod) == 1
        )
    )
    return num, mod


@st.composite
def st_primes(draw, *args, **kwargs):
    if "min_value" not in kwargs:  # pragma: no branch
        kwargs["min_value"] = 1
    prime = draw(
        st.sampled_from(smallprimes)
        | st.integers(*args, **kwargs).filter(is_prime)
    )
    return prime


@st.composite
def st_num_square_prime(draw):
    prime = draw(st_primes(max_value=2**1024))
    num = draw(st.integers(min_value=0, max_value=1 + prime // 2))
    sq = num * num % prime
    return sq, prime


@st.composite
def st_comp_with_com_fac(draw):
    """
    Strategy that returns lists of numbers, all having a common factor.
    """
    primes = draw(
        st.lists(st_primes(max_value=2**512), min_size=1, max_size=10)
    )
    # select random prime(s) that will make the common factor of composites
    com_fac_primes = draw(
        st.lists(st.sampled_from(primes), min_size=1, max_size=20)
    )
    com_fac = reduce(operator.mul, com_fac_primes, 1)

    # select at most 20 lists (returned numbers),
    # each having at most 30 primes (factors) including none (then the number
    # will be 1)
    comp_primes = draw(  # pragma: no branch
        st.integers(min_value=1, max_value=20).flatmap(
            lambda n: st.lists(
                st.lists(st.sampled_from(primes), max_size=30),
                min_size=1,
                max_size=n,
            )
        )
    )

    return [reduce(operator.mul, nums, 1) * com_fac for nums in comp_primes]


@st.composite
def st_comp_no_com_fac(draw):
    """
    Strategy that returns lists of numbers that don't have a common factor.
    """
    primes = draw(
        st.lists(
            st_primes(max_value=2**512), min_size=2, max_size=10, unique=True
        )
    )
    # first select the primes that will create the uncommon factor
    # between returned numbers
    uncom_fac_primes = draw(
        st.lists(
            st.sampled_from(primes),
            min_size=1,
            max_size=len(primes) - 1,
            unique=True,
        )
    )
    uncom_fac = reduce(operator.mul, uncom_fac_primes, 1)

    # then build composites from leftover primes
    leftover_primes = [i for i in primes if i not in uncom_fac_primes]

    assert leftover_primes
    assert uncom_fac_primes

    # select at most 20 lists, each having at most 30 primes
    # selected from the leftover_primes list
    number_primes = draw(  # pragma: no branch
        st.integers(min_value=1, max_value=20).flatmap(
            lambda n: st.lists(
                st.lists(st.sampled_from(leftover_primes), max_size=30),
                min_size=1,
                max_size=n,
            )
        )
    )

    numbers = [reduce(operator.mul, nums, 1) for nums in number_primes]

    insert_at = draw(st.integers(min_value=0, max_value=len(numbers)))
    numbers.insert(insert_at, uncom_fac)
    return numbers


HYP_SETTINGS = {}
if HC_PRESENT:  # pragma: no branch
    HYP_SETTINGS["suppress_health_check"] = [
        HealthCheck.filter_too_much,
        HealthCheck.too_slow,
    ]
    # the factorization() sometimes takes a long time to finish
    HYP_SETTINGS["deadline"] = 5000

if "--fast" in sys.argv:  # pragma: no cover
    HYP_SETTINGS["max_examples"] = 20


HYP_SLOW_SETTINGS = dict(HYP_SETTINGS)
if "--fast" in sys.argv:  # pragma: no cover
    HYP_SLOW_SETTINGS["max_examples"] = 1
else:
    HYP_SLOW_SETTINGS["max_examples"] = 20


class TestIsPrime(unittest.TestCase):
    def test_very_small_prime(self):
        assert is_prime(23)

    def test_very_small_composite(self):
        assert not is_prime(22)

    def test_small_prime(self):
        assert is_prime(123456791)

    def test_special_composite(self):
        assert not is_prime(10261)

    def test_medium_prime_1(self):
        # nextPrime[2^256]
        assert is_prime(2**256 + 0x129)

    def test_medium_prime_2(self):
        # nextPrime(2^256+0x129)
        assert is_prime(2**256 + 0x12D)

    def test_medium_trivial_composite(self):
        assert not is_prime(2**256 + 0x130)

    def test_medium_non_trivial_composite(self):
        assert not is_prime(2**256 + 0x12F)

    def test_large_prime(self):
        # nextPrime[2^2048]
        assert is_prime(mpz(2) ** 2048 + 0x3D5)

    def test_pseudoprime_base_19(self):
        assert not is_prime(1543267864443420616877677640751301)

    def test_pseudoprime_base_300(self):
        # F. Arnault "Constructing Carmichael Numbers Which Are Strong
        # Pseudoprimes to Several Bases". Journal of Symbolic
        # Computation. 20 (2): 151-161. doi:10.1006/jsco.1995.1042.
        # Section 4.4 Large Example (a pseudoprime to all bases up to
        # 300)
        p = int(
            "29 674 495 668 685 510 550 154 174 642 905 332 730 "
            "771 991 799 853 043 350 995 075 531 276 838 753 171 "
            "770 199 594 238 596 428 121 188 033 664 754 218 345 "
            "562 493 168 782 883".replace(" ", "")
        )

        assert is_prime(p)
        for _ in range(10):
            if not is_prime(p * (313 * (p - 1) + 1) * (353 * (p - 1) + 1)):
                break
        else:
            assert False, "composite not detected"


class TestNumbertheory(unittest.TestCase):
    def test_gcd(self):
        assert gcd(3 * 5 * 7, 3 * 5 * 11, 3 * 5 * 13) == 3 * 5
        assert gcd([3 * 5 * 7, 3 * 5 * 11, 3 * 5 * 13]) == 3 * 5
        assert gcd(3) == 3

    @unittest.skipUnless(
        HC_PRESENT,
        "Hypothesis 2.0.0 can't be made tolerant of hard to "
        "meet requirements (like `is_prime()`), the test "
        "case times-out on it",
    )
    @settings(**HYP_SLOW_SETTINGS)
    @example([877 * 1151, 877 * 1009])
    @given(st_comp_with_com_fac())
    def test_gcd_with_com_factor(self, numbers):
        n = gcd(numbers)
        assert 1 in numbers or n != 1
        for i in numbers:
            assert i % n == 0

    @unittest.skipUnless(
        HC_PRESENT,
        "Hypothesis 2.0.0 can't be made tolerant of hard to "
        "meet requirements (like `is_prime()`), the test "
        "case times-out on it",
    )
    @settings(**HYP_SLOW_SETTINGS)
    @example([1151, 1069, 1009])
    @given(st_comp_no_com_fac())
    def test_gcd_with_uncom_factor(self, numbers):
        n = gcd(numbers)
        assert n == 1

    @settings(**HYP_SLOW_SETTINGS)
    @given(
        st.lists(
            st.integers(min_value=1, max_value=2**8192),
            min_size=1,
            max_size=20,
        )
    )
    def test_gcd_with_random_numbers(self, numbers):
        n = gcd(numbers)
        for i in numbers:
            # check that at least it's a divider
            assert i % n == 0

    def test_lcm(self):
        assert lcm(3, 5 * 3, 7 * 3) == 3 * 5 * 7
        assert lcm([3, 5 * 3, 7 * 3]) == 3 * 5 * 7
        assert lcm(3) == 3

    @settings(**HYP_SLOW_SETTINGS)
    @given(
        st.lists(
            st.integers(min_value=1, max_value=2**8192),
            min_size=1,
            max_size=20,
        )
    )
    def test_lcm_with_random_numbers(self, numbers):
        n = lcm(numbers)
        for i in numbers:
            assert n % i == 0

    @unittest.skipUnless(
        HC_PRESENT,
        "Hypothesis 2.0.0 can't be made tolerant of hard to "
        "meet requirements (like `is_prime()`), the test "
        "case times-out on it",
    )
    @settings(**HYP_SLOW_SETTINGS)
    @given(st_num_square_prime())
    def test_square_root_mod_prime(self, vals):
        square, prime = vals

        calc = square_root_mod_prime(square, prime)
        assert calc * calc % prime == square

    @pytest.mark.slow
    @settings(**HYP_SLOW_SETTINGS)
    @given(st.integers(min_value=1, max_value=10**12))
    @example(265399 * 1526929)
    @example(373297**2 * 553991)
    def test_factorization(self, num):
        factors = factorization(num)
        mult = 1
        for i in factors:
            mult *= i[0] ** i[1]
        assert mult == num

    def test_factorisation_smallprimes(self):
        exp = 101 * 103
        assert 101 in smallprimes
        assert 103 in smallprimes
        factors = factorization(exp)
        mult = 1
        for i in factors:
            mult *= i[0] ** i[1]
        assert mult == exp

    def test_factorisation_not_smallprimes(self):
        exp = 1231 * 1237
        assert 1231 not in smallprimes
        assert 1237 not in smallprimes
        factors = factorization(exp)
        mult = 1
        for i in factors:
            mult *= i[0] ** i[1]
        assert mult == exp

    def test_jacobi_with_zero(self):
        assert jacobi(0, 3) == 0

    def test_jacobi_with_one(self):
        assert jacobi(1, 3) == 1

    @settings(**HYP_SLOW_SETTINGS)
    @given(st.integers(min_value=3, max_value=1000).filter(lambda x: x % 2))
    def test_jacobi(self, mod):
        mod = mpz(mod)
        if is_prime(mod):
            squares = set()
            for root in range(1, mod):
                root = mpz(root)
                assert jacobi(root * root, mod) == 1
                squares.add(root * root % mod)
            for i in range(1, mod):
                if i not in squares:
                    i = mpz(i)
                    assert jacobi(i, mod) == -1
        else:
            factors = factorization(mod)
            for a in range(1, mod):
                c = 1
                for i in factors:
                    c *= jacobi(a, i[0]) ** i[1]
                assert c == jacobi(a, mod)

    @settings(**HYP_SLOW_SETTINGS)
    @given(st_two_nums_rel_prime())
    def test_inverse_mod(self, nums):
        num, mod = nums

        inv = inverse_mod(num, mod)

        assert 0 < inv < mod
        assert num * inv % mod == 1

    def test_inverse_mod_with_zero(self):
        assert 0 == inverse_mod(0, 11)

1	import operator	20✔
2	from functools import reduce	20✔
3	import sys	20✔
4
5	try:	20✔
6	import unittest2 as unittest	20✔
7	except ImportError:	19✔
8	import unittest	19✔
9	import hypothesis.strategies as st	20✔
10	import pytest	20✔
11	from hypothesis import given, settings, example	20✔
12
13	try:	20✔
14	from hypothesis import HealthCheck	20✔
15
16	HC_PRESENT = True	19✔
17	except ImportError: # pragma: no cover
18	HC_PRESENT = False
19	from .numbertheory import (	20✔
20	SquareRootError,
21	JacobiError,
22	factorization,
23	gcd,
24	lcm,
25	jacobi,
26	inverse_mod,
27	is_prime,
28	next_prime,
29	smallprimes,
30	square_root_mod_prime,
31	)
32
33	try:	20✔
34	from gmpy2 import mpz	20✔
35	except ImportError:	17✔
36	try:	17✔
37	from gmpy import mpz	17✔
38	except ImportError:	14✔
39
40	def mpz(x):	14✔
41	return x	14✔
42
43
44	BIGPRIMES = (	20✔
45	999671,
46	999683,
47	999721,
48	999727,
49	999749,
50	999763,
51	999769,
52	999773,
53	999809,
54	999853,
55	999863,
56	999883,
57	999907,
58	999917,
59	999931,
60	999953,
61	999959,
62	999961,
63	999979,
64	999983,
65	)
66
67
68	@pytest.mark.parametrize(	20✔
69	"prime, next_p", [(p, q) for p, q in zip(BIGPRIMES[:-1], BIGPRIMES[1:])]
70	)
71	def test_next_prime(prime, next_p):	9✔
72	assert next_prime(prime) == next_p	20✔
73
74
75	@pytest.mark.parametrize("val", [-1, 0, 1])	20✔
76	def test_next_prime_with_nums_less_2(val):	9✔
77	assert next_prime(val) == 2	20✔
78
79
80	@pytest.mark.slow	20✔
81	@pytest.mark.parametrize("prime", smallprimes)	20✔
82	def test_square_root_mod_prime_for_small_primes(prime):	9✔
83	squares = set()	20✔
84	for num in range(0, 1 + prime // 2):	20✔
85	sq = num * num % prime	20✔
86	squares.add(sq)	20✔
87	root = square_root_mod_prime(sq, prime)	20✔
88	# tested for real with TestNumbertheory.test_square_root_mod_prime
89	assert root * root % prime == sq	20✔
90
91	for nonsquare in range(0, prime):	20✔
92	if nonsquare in squares:	20✔
93	continue	20✔
94	with pytest.raises(SquareRootError):	20✔
95	square_root_mod_prime(nonsquare, prime)	20✔
96
97
98	def test_square_root_mod_prime_for_2():	20✔
99	a = square_root_mod_prime(1, 2)	20✔
100	assert a == 1	20✔
101
102
103	def test_square_root_mod_prime_for_small_prime():	20✔
104	root = square_root_mod_prime(98**2 % 101, 101)	20✔
105	assert root * root % 101 == 9	20✔
106
107
108	def test_square_root_mod_prime_for_p_congruent_5():	20✔
109	p = 13	20✔
110	assert p % 8 == 5	20✔
111
112	root = square_root_mod_prime(3, p)	20✔
113	assert root * root % p == 3	20✔
114
115
116	def test_square_root_mod_prime_for_p_congruent_5_large_d():	20✔
117	p = 29	20✔
118	assert p % 8 == 5	20✔
119
120	root = square_root_mod_prime(4, p)	20✔
121	assert root * root % p == 4	20✔
122
123
124	class TestSquareRootModPrime(unittest.TestCase):	20✔
125	def test_power_of_2_p(self):	20✔
126	with self.assertRaises(JacobiError):	20✔
127	square_root_mod_prime(12, 32)	20✔
128
129	def test_no_square(self):	20✔
130	with self.assertRaises(SquareRootError) as e:	20✔
131	square_root_mod_prime(12, 31)	20✔
132
133	self.assertIn("no square root", str(e.exception))	20✔
134
135	def test_non_prime(self):	20✔
136	with self.assertRaises(SquareRootError) as e:	20✔
137	square_root_mod_prime(12, 33)	20✔
138
139	self.assertIn("p is not prime", str(e.exception))	20✔
140
141	def test_non_prime_with_negative(self):	20✔
142	with self.assertRaises(SquareRootError) as e:	20✔
143	square_root_mod_prime(697 - 1, 697)	20✔
144
145	self.assertIn("p is not prime", str(e.exception))	20✔
146
147
148	@st.composite	20✔
149	def st_two_nums_rel_prime(draw):	9✔
150	# 521-bit is the biggest curve we operate on, use 1024 for a bit
151	# of breathing space
152	mod = draw(st.integers(min_value=2, max_value=2**1024))	20✔
153	num = draw(	20✔
154	st.integers(min_value=1, max_value=mod - 1).filter(
155	lambda x: gcd(x, mod) == 1
156	)
157	)
158	return num, mod	20✔
159
160
161	@st.composite	20✔
162	def st_primes(draw, args, *kwargs):	9✔
163	if "min_value" not in kwargs: # pragma: no branch	19✔
164	kwargs["min_value"] = 1	19✔
165	prime = draw(	19✔
166	st.sampled_from(smallprimes)
167	\| st.integers(args, *kwargs).filter(is_prime)
168	)
169	return prime	19✔
170
171
172	@st.composite	20✔
173	def st_num_square_prime(draw):	9✔
174	prime = draw(st_primes(max_value=2**1024))	19✔
175	num = draw(st.integers(min_value=0, max_value=1 + prime // 2))	19✔
176	sq = num * num % prime	19✔
177	return sq, prime	19✔
178
179
180	@st.composite	20✔
181	def st_comp_with_com_fac(draw):	9✔
182	"""
183	Strategy that returns lists of numbers, all having a common factor.
184	"""
185	primes = draw(	19✔
186	st.lists(st_primes(max_value=2**512), min_size=1, max_size=10)
187	)
188	# select random prime(s) that will make the common factor of composites
189	com_fac_primes = draw(	19✔
190	st.lists(st.sampled_from(primes), min_size=1, max_size=20)
191	)
192	com_fac = reduce(operator.mul, com_fac_primes, 1)	19✔
193
194	# select at most 20 lists (returned numbers),
195	# each having at most 30 primes (factors) including none (then the number
196	# will be 1)
197	comp_primes = draw( # pragma: no branch	19✔
198	st.integers(min_value=1, max_value=20).flatmap(
199	lambda n: st.lists(
200	st.lists(st.sampled_from(primes), max_size=30),
201	min_size=1,
202	max_size=n,
203	)
204	)
205	)
206
207	return [reduce(operator.mul, nums, 1) * com_fac for nums in comp_primes]	19✔
208
209
210	@st.composite	20✔
211	def st_comp_no_com_fac(draw):	9✔
212	"""
213	Strategy that returns lists of numbers that don't have a common factor.
214	"""
215	primes = draw(	19✔
216	st.lists(
217	st_primes(max_value=2**512), min_size=2, max_size=10, unique=True
218	)
219	)
220	# first select the primes that will create the uncommon factor
221	# between returned numbers
222	uncom_fac_primes = draw(	19✔
223	st.lists(
224	st.sampled_from(primes),
225	min_size=1,
226	max_size=len(primes) - 1,
227	unique=True,
228	)
229	)
230	uncom_fac = reduce(operator.mul, uncom_fac_primes, 1)	19✔
231
232	# then build composites from leftover primes
233	leftover_primes = [i for i in primes if i not in uncom_fac_primes]	19✔
234
235	assert leftover_primes	19✔
236	assert uncom_fac_primes	19✔
237
238	# select at most 20 lists, each having at most 30 primes
239	# selected from the leftover_primes list
240	number_primes = draw( # pragma: no branch	19✔
241	st.integers(min_value=1, max_value=20).flatmap(
242	lambda n: st.lists(
243	st.lists(st.sampled_from(leftover_primes), max_size=30),
244	min_size=1,
245	max_size=n,
246	)
247	)
248	)
249
250	numbers = [reduce(operator.mul, nums, 1) for nums in number_primes]	19✔
251
252	insert_at = draw(st.integers(min_value=0, max_value=len(numbers)))	19✔
253	numbers.insert(insert_at, uncom_fac)	19✔
254	return numbers	19✔
255
256
257	HYP_SETTINGS = {}	20✔
258	if HC_PRESENT: # pragma: no branch	20✔
259	HYP_SETTINGS["suppress_health_check"] = [	19✔
260	HealthCheck.filter_too_much,
261	HealthCheck.too_slow,
262	]
263	# the factorization() sometimes takes a long time to finish
264	HYP_SETTINGS["deadline"] = 5000	19✔
265
266	if "--fast" in sys.argv: # pragma: no cover
267	HYP_SETTINGS["max_examples"] = 20
268
269
270	HYP_SLOW_SETTINGS = dict(HYP_SETTINGS)	20✔
271	if "--fast" in sys.argv: # pragma: no cover
272	HYP_SLOW_SETTINGS["max_examples"] = 1
273	else:
274	HYP_SLOW_SETTINGS["max_examples"] = 20	20✔
275
276
277	class TestIsPrime(unittest.TestCase):	20✔
278	def test_very_small_prime(self):	20✔
279	assert is_prime(23)	20✔
280
281	def test_very_small_composite(self):	20✔
282	assert not is_prime(22)	20✔
283
284	def test_small_prime(self):	20✔
285	assert is_prime(123456791)	20✔
286
287	def test_special_composite(self):	20✔
288	assert not is_prime(10261)	20✔
289
290	def test_medium_prime_1(self):	20✔
291	# nextPrime[2^256]
292	assert is_prime(2**256 + 0x129)	20✔
293
294	def test_medium_prime_2(self):	20✔
295	# nextPrime(2^256+0x129)
296	assert is_prime(2**256 + 0x12D)	20✔
297
298	def test_medium_trivial_composite(self):	20✔
299	assert not is_prime(2**256 + 0x130)	20✔
300
301	def test_medium_non_trivial_composite(self):	20✔
302	assert not is_prime(2**256 + 0x12F)	20✔
303
304	def test_large_prime(self):	20✔
305	# nextPrime[2^2048]
306	assert is_prime(mpz(2) ** 2048 + 0x3D5)	20✔
307
308	def test_pseudoprime_base_19(self):	20✔
309	assert not is_prime(1543267864443420616877677640751301)	20✔
310
311	def test_pseudoprime_base_300(self):	20✔
312	# F. Arnault "Constructing Carmichael Numbers Which Are Strong
313	# Pseudoprimes to Several Bases". Journal of Symbolic
314	# Computation. 20 (2): 151-161. doi:10.1006/jsco.1995.1042.
315	# Section 4.4 Large Example (a pseudoprime to all bases up to
316	# 300)
317	p = int(	20✔
318	"29 674 495 668 685 510 550 154 174 642 905 332 730 "
319	"771 991 799 853 043 350 995 075 531 276 838 753 171 "
320	"770 199 594 238 596 428 121 188 033 664 754 218 345 "
321	"562 493 168 782 883".replace(" ", "")
322	)
323
324	assert is_prime(p)	20✔
325	for _ in range(10):	20!
326	if not is_prime(p * (313 * (p - 1) + 1) * (353 * (p - 1) + 1)):	20✔
327	break	20✔
328	else:
329	assert False, "composite not detected"	×
330
331
332	class TestNumbertheory(unittest.TestCase):	20✔
333	def test_gcd(self):	20✔
334	assert gcd(3 * 5 * 7, 3 * 5 * 11, 3 * 5 * 13) == 3 * 5	20✔
335	assert gcd([3 * 5 * 7, 3 * 5 * 11, 3 * 5 * 13]) == 3 * 5	20✔
336	assert gcd(3) == 3	20✔
337
338	@unittest.skipUnless(	20✔
339	HC_PRESENT,
340	"Hypothesis 2.0.0 can't be made tolerant of hard to "
341	"meet requirements (like `is_prime()`), the test "
342	"case times-out on it",
343	)
344	@settings(**HYP_SLOW_SETTINGS)	20✔
345	@example([877 * 1151, 877 * 1009])	20✔
346	@given(st_comp_with_com_fac())	20✔
347	def test_gcd_with_com_factor(self, numbers):	9✔
348	n = gcd(numbers)	19✔
349	assert 1 in numbers or n != 1	19✔
350	for i in numbers:	19✔
351	assert i % n == 0	19✔
352
353	@unittest.skipUnless(	20✔
354	HC_PRESENT,
355	"Hypothesis 2.0.0 can't be made tolerant of hard to "
356	"meet requirements (like `is_prime()`), the test "
357	"case times-out on it",
358	)
359	@settings(**HYP_SLOW_SETTINGS)	20✔
360	@example([1151, 1069, 1009])	20✔
361	@given(st_comp_no_com_fac())	20✔
362	def test_gcd_with_uncom_factor(self, numbers):	9✔
363	n = gcd(numbers)	19✔
364	assert n == 1	19✔
365
366	@settings(**HYP_SLOW_SETTINGS)	20✔
367	@given(	20✔
368	st.lists(
369	st.integers(min_value=1, max_value=2**8192),
370	min_size=1,
371	max_size=20,
372	)
373	)
374	def test_gcd_with_random_numbers(self, numbers):	9✔
375	n = gcd(numbers)	20✔
376	for i in numbers:	20✔
377	# check that at least it's a divider
378	assert i % n == 0	20✔
379
380	def test_lcm(self):	20✔
381	assert lcm(3, 5 * 3, 7 * 3) == 3 * 5 * 7	20✔
382	assert lcm([3, 5 * 3, 7 * 3]) == 3 * 5 * 7	20✔
383	assert lcm(3) == 3	20✔
384
385	@settings(**HYP_SLOW_SETTINGS)	20✔
386	@given(	20✔
387	st.lists(
388	st.integers(min_value=1, max_value=2**8192),
389	min_size=1,
390	max_size=20,
391	)
392	)
393	def test_lcm_with_random_numbers(self, numbers):	9✔
394	n = lcm(numbers)	20✔
395	for i in numbers:	20✔
396	assert n % i == 0	20✔
397
398	@unittest.skipUnless(	20✔
399	HC_PRESENT,
400	"Hypothesis 2.0.0 can't be made tolerant of hard to "
401	"meet requirements (like `is_prime()`), the test "
402	"case times-out on it",
403	)
404	@settings(**HYP_SLOW_SETTINGS)	20✔
405	@given(st_num_square_prime())	20✔
406	def test_square_root_mod_prime(self, vals):	9✔
407	square, prime = vals	19✔
408
409	calc = square_root_mod_prime(square, prime)	19✔
410	assert calc * calc % prime == square	19✔
411
412	@pytest.mark.slow	20✔
413	@settings(**HYP_SLOW_SETTINGS)	20✔
414	@given(st.integers(min_value=1, max_value=10**12))	20✔
415	@example(265399 * 1526929)	20✔
416	@example(373297*2 553991)	20✔
417	def test_factorization(self, num):	9✔
418	factors = factorization(num)	20✔
419	mult = 1	20✔
420	for i in factors:	20✔
421	mult = i[0] * i[1]	20✔
422	assert mult == num	20✔
423
424	def test_factorisation_smallprimes(self):	20✔
425	exp = 101 * 103	20✔
426	assert 101 in smallprimes	20✔
427	assert 103 in smallprimes	20✔
428	factors = factorization(exp)	20✔
429	mult = 1	20✔
430	for i in factors:	20✔
431	mult = i[0] * i[1]	20✔
432	assert mult == exp	20✔
433
434	def test_factorisation_not_smallprimes(self):	20✔
435	exp = 1231 * 1237	20✔
436	assert 1231 not in smallprimes	20✔
437	assert 1237 not in smallprimes	20✔
438	factors = factorization(exp)	20✔
439	mult = 1	20✔
440	for i in factors:	20✔
441	mult = i[0] * i[1]	20✔
442	assert mult == exp	20✔
443
444	def test_jacobi_with_zero(self):	20✔
445	assert jacobi(0, 3) == 0	20✔
446
447	def test_jacobi_with_one(self):	20✔
448	assert jacobi(1, 3) == 1	20✔
449
450	@settings(**HYP_SLOW_SETTINGS)	20✔
451	@given(st.integers(min_value=3, max_value=1000).filter(lambda x: x % 2))	20✔
452	def test_jacobi(self, mod):	9✔
453	mod = mpz(mod)	20✔
454	if is_prime(mod):	20✔
455	squares = set()	20✔
456	for root in range(1, mod):	20✔
457	root = mpz(root)	20✔
458	assert jacobi(root * root, mod) == 1	20✔
459	squares.add(root * root % mod)	20✔
460	for i in range(1, mod):	20✔
461	if i not in squares:	20✔
462	i = mpz(i)	20✔
463	assert jacobi(i, mod) == -1	20✔
464	else:
465	factors = factorization(mod)	20✔
466	for a in range(1, mod):	20✔
467	c = 1	20✔
468	for i in factors:	20✔
469	c = jacobi(a, i[0]) * i[1]	20✔
470	assert c == jacobi(a, mod)	20✔
471
472	@settings(**HYP_SLOW_SETTINGS)	20✔
473	@given(st_two_nums_rel_prime())	20✔
474	def test_inverse_mod(self, nums):	9✔
475	num, mod = nums	20✔
476
477	inv = inverse_mod(num, mod)	20✔
478
479	assert 0 < inv < mod	20✔
480	assert num * inv % mod == 1	20✔
481
482	def test_inverse_mod_with_zero(self):	20✔
483	assert 0 == inverse_mod(0, 11)	20✔

tlsfuzzer / python-ecdsa / 13832902924

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous