From 3bef51eec2299403467e621ae660cef3f9256ac8 Mon Sep 17 00:00:00 2001 From: Determinant Date: Tue, 17 Nov 2020 18:47:40 -0500 Subject: update frozen deps --- freezed_deps/ecdsa/numbertheory.py | 600 ------------------------------------- 1 file changed, 600 deletions(-) delete mode 100644 freezed_deps/ecdsa/numbertheory.py (limited to 'freezed_deps/ecdsa/numbertheory.py') diff --git a/freezed_deps/ecdsa/numbertheory.py b/freezed_deps/ecdsa/numbertheory.py deleted file mode 100644 index b300440..0000000 --- a/freezed_deps/ecdsa/numbertheory.py +++ /dev/null @@ -1,600 +0,0 @@ -#! /usr/bin/env python -# -# Provide some simple capabilities from number theory. -# -# Version of 2008.11.14. -# -# Written in 2005 and 2006 by Peter Pearson and placed in the public domain. -# Revision history: -# 2008.11.14: Use pow(base, exponent, modulus) for modular_exp. -# Make gcd and lcm accept arbitrarly many arguments. - -from __future__ import division - -from six import integer_types, PY3 -from six.moves import reduce -try: - xrange -except NameError: - xrange = range -try: - from gmpy2 import powmod - GMPY2 = True - GMPY = False -except ImportError: - GMPY2 = False - try: - from gmpy import mpz - GMPY = True - except ImportError: - GMPY = False - -import math -import warnings - - -class Error(Exception): - """Base class for exceptions in this module.""" - pass - - -class SquareRootError(Error): - pass - - -class NegativeExponentError(Error): - pass - - -def modular_exp(base, exponent, modulus): # pragma: no cover - """Raise base to exponent, reducing by modulus""" - # deprecated in 0.14 - warnings.warn("Function is unused in library code. If you use this code, " - "change to pow() builtin.", DeprecationWarning) - if exponent < 0: - raise NegativeExponentError("Negative exponents (%d) not allowed" - % exponent) - return pow(base, exponent, modulus) - - -def polynomial_reduce_mod(poly, polymod, p): - """Reduce poly by polymod, integer arithmetic modulo p. - - Polynomials are represented as lists of coefficients - of increasing powers of x.""" - - # This module has been tested only by extensive use - # in calculating modular square roots. - - # Just to make this easy, require a monic polynomial: - assert polymod[-1] == 1 - - assert len(polymod) > 1 - - while len(poly) >= len(polymod): - if poly[-1] != 0: - for i in xrange(2, len(polymod) + 1): - poly[-i] = (poly[-i] - poly[-1] * polymod[-i]) % p - poly = poly[0:-1] - - return poly - - -def polynomial_multiply_mod(m1, m2, polymod, p): - """Polynomial multiplication modulo a polynomial over ints mod p. - - Polynomials are represented as lists of coefficients - of increasing powers of x.""" - - # This is just a seat-of-the-pants implementation. - - # This module has been tested only by extensive use - # in calculating modular square roots. - - # Initialize the product to zero: - - prod = (len(m1) + len(m2) - 1) * [0] - - # Add together all the cross-terms: - - for i in xrange(len(m1)): - for j in xrange(len(m2)): - prod[i + j] = (prod[i + j] + m1[i] * m2[j]) % p - - return polynomial_reduce_mod(prod, polymod, p) - - -def polynomial_exp_mod(base, exponent, polymod, p): - """Polynomial exponentiation modulo a polynomial over ints mod p. - - Polynomials are represented as lists of coefficients - of increasing powers of x.""" - - # Based on the Handbook of Applied Cryptography, algorithm 2.227. - - # This module has been tested only by extensive use - # in calculating modular square roots. - - assert exponent < p - - if exponent == 0: - return [1] - - G = base - k = exponent - if k % 2 == 1: - s = G - else: - s = [1] - - while k > 1: - k = k // 2 - G = polynomial_multiply_mod(G, G, polymod, p) - if k % 2 == 1: - s = polynomial_multiply_mod(G, s, polymod, p) - - return s - - -def jacobi(a, n): - """Jacobi symbol""" - - # Based on the Handbook of Applied Cryptography (HAC), algorithm 2.149. - - # This function has been tested by comparison with a small - # table printed in HAC, and by extensive use in calculating - # modular square roots. - - assert n >= 3 - assert n % 2 == 1 - a = a % n - if a == 0: - return 0 - if a == 1: - return 1 - a1, e = a, 0 - while a1 % 2 == 0: - a1, e = a1 // 2, e + 1 - if e % 2 == 0 or n % 8 == 1 or n % 8 == 7: - s = 1 - else: - s = -1 - if a1 == 1: - return s - if n % 4 == 3 and a1 % 4 == 3: - s = -s - return s * jacobi(n % a1, a1) - - -def square_root_mod_prime(a, p): - """Modular square root of a, mod p, p prime.""" - - # Based on the Handbook of Applied Cryptography, algorithms 3.34 to 3.39. - - # This module has been tested for all values in [0,p-1] for - # every prime p from 3 to 1229. - - assert 0 <= a < p - assert 1 < p - - if a == 0: - return 0 - if p == 2: - return a - - jac = jacobi(a, p) - if jac == -1: - raise SquareRootError("%d has no square root modulo %d" \ - % (a, p)) - - if p % 4 == 3: - return pow(a, (p + 1) // 4, p) - - if p % 8 == 5: - d = pow(a, (p - 1) // 4, p) - if d == 1: - return pow(a, (p + 3) // 8, p) - if d == p - 1: - return (2 * a * pow(4 * a, (p - 5) // 8, p)) % p - raise RuntimeError("Shouldn't get here.") - - if PY3: - range_top = p - else: - # xrange on python2 can take integers representable as C long only - range_top = min(0x7fffffff, p) - for b in xrange(2, range_top): - if jacobi(b * b - 4 * a, p) == -1: - f = (a, -b, 1) - ff = polynomial_exp_mod((0, 1), (p + 1) // 2, f, p) - assert ff[1] == 0 - return ff[0] - raise RuntimeError("No b found.") - - -if GMPY2: - def inverse_mod(a, m): - """Inverse of a mod m.""" - if a == 0: - return 0 - return powmod(a, -1, m) -elif GMPY: - def inverse_mod(a, m): - """Inverse of a mod m.""" - # while libgmp likely does support inverses modulo, it is accessible - # only using the native `pow()` function, and `pow()` sanity checks - # the parameters before passing them on to underlying implementation - # on Python2 - if a == 0: - return 0 - a = mpz(a) - m = mpz(m) - - lm, hm = mpz(1), mpz(0) - low, high = a % m, m - while low > 1: - r = high // low - lm, low, hm, high = hm - lm * r, high - low * r, lm, low - - return lm % m -else: - def inverse_mod(a, m): - """Inverse of a mod m.""" - - if a == 0: - return 0 - - lm, hm = 1, 0 - low, high = a % m, m - while low > 1: - r = high // low - lm, low, hm, high = hm - lm * r, high - low * r, lm, low - - return lm % m - - -try: - gcd2 = math.gcd -except AttributeError: - def gcd2(a, b): - """Greatest common divisor using Euclid's algorithm.""" - while a: - a, b = b % a, a - return b - - -def gcd(*a): - """Greatest common divisor. - - Usage: gcd([ 2, 4, 6 ]) - or: gcd(2, 4, 6) - """ - - if len(a) > 1: - return reduce(gcd2, a) - if hasattr(a[0], "__iter__"): - return reduce(gcd2, a[0]) - return a[0] - - -def lcm2(a, b): - """Least common multiple of two integers.""" - - return (a * b) // gcd(a, b) - - -def lcm(*a): - """Least common multiple. - - Usage: lcm([ 3, 4, 5 ]) - or: lcm(3, 4, 5) - """ - - if len(a) > 1: - return reduce(lcm2, a) - if hasattr(a[0], "__iter__"): - return reduce(lcm2, a[0]) - return a[0] - - -def factorization(n): - """Decompose n into a list of (prime,exponent) pairs.""" - - assert isinstance(n, integer_types) - - if n < 2: - return [] - - result = [] - d = 2 - - # Test the small primes: - - for d in smallprimes: - if d > n: - break - q, r = divmod(n, d) - if r == 0: - count = 1 - while d <= n: - n = q - q, r = divmod(n, d) - if r != 0: - break - count = count + 1 - result.append((d, count)) - - # If n is still greater than the last of our small primes, - # it may require further work: - - if n > smallprimes[-1]: - if is_prime(n): # If what's left is prime, it's easy: - result.append((n, 1)) - else: # Ugh. Search stupidly for a divisor: - d = smallprimes[-1] - while 1: - d = d + 2 # Try the next divisor. - q, r = divmod(n, d) - if q < d: # n < d*d means we're done, n = 1 or prime. - break - if r == 0: # d divides n. How many times? - count = 1 - n = q - while d <= n: # As long as d might still divide n, - q, r = divmod(n, d) # see if it does. - if r != 0: - break - n = q # It does. Reduce n, increase count. - count = count + 1 - result.append((d, count)) - if n > 1: - result.append((n, 1)) - - return result - - -def phi(n): # pragma: no cover - """Return the Euler totient function of n.""" - # deprecated in 0.14 - warnings.warn("Function is unused by library code. If you use this code, " - "please open an issue in " - "https://github.com/warner/python-ecdsa", - DeprecationWarning) - - assert isinstance(n, integer_types) - - if n < 3: - return 1 - - result = 1 - ff = factorization(n) - for f in ff: - e = f[1] - if e > 1: - result = result * f[0] ** (e - 1) * (f[0] - 1) - else: - result = result * (f[0] - 1) - return result - - -def carmichael(n): # pragma: no cover - """Return Carmichael function of n. - - Carmichael(n) is the smallest integer x such that - m**x = 1 mod n for all m relatively prime to n. - """ - # deprecated in 0.14 - warnings.warn("Function is unused by library code. If you use this code, " - "please open an issue in " - "https://github.com/warner/python-ecdsa", - DeprecationWarning) - - return carmichael_of_factorized(factorization(n)) - - -def carmichael_of_factorized(f_list): # pragma: no cover - """Return the Carmichael function of a number that is - represented as a list of (prime,exponent) pairs. - """ - # deprecated in 0.14 - warnings.warn("Function is unused by library code. If you use this code, " - "please open an issue in " - "https://github.com/warner/python-ecdsa", - DeprecationWarning) - - if len(f_list) < 1: - return 1 - - result = carmichael_of_ppower(f_list[0]) - for i in xrange(1, len(f_list)): - result = lcm(result, carmichael_of_ppower(f_list[i])) - - return result - - -def carmichael_of_ppower(pp): # pragma: no cover - """Carmichael function of the given power of the given prime. - """ - # deprecated in 0.14 - warnings.warn("Function is unused by library code. If you use this code, " - "please open an issue in " - "https://github.com/warner/python-ecdsa", - DeprecationWarning) - - p, a = pp - if p == 2 and a > 2: - return 2**(a - 2) - else: - return (p - 1) * p**(a - 1) - - -def order_mod(x, m): # pragma: no cover - """Return the order of x in the multiplicative group mod m. - """ - # deprecated in 0.14 - warnings.warn("Function is unused by library code. If you use this code, " - "please open an issue in " - "https://github.com/warner/python-ecdsa", - DeprecationWarning) - - # Warning: this implementation is not very clever, and will - # take a long time if m is very large. - - if m <= 1: - return 0 - - assert gcd(x, m) == 1 - - z = x - result = 1 - while z != 1: - z = (z * x) % m - result = result + 1 - return result - - -def largest_factor_relatively_prime(a, b): # pragma: no cover - """Return the largest factor of a relatively prime to b. - """ - # deprecated in 0.14 - warnings.warn("Function is unused by library code. If you use this code, " - "please open an issue in " - "https://github.com/warner/python-ecdsa", - DeprecationWarning) - - while 1: - d = gcd(a, b) - if d <= 1: - break - b = d - while 1: - q, r = divmod(a, d) - if r > 0: - break - a = q - return a - - -def kinda_order_mod(x, m): # pragma: no cover - """Return the order of x in the multiplicative group mod m', - where m' is the largest factor of m relatively prime to x. - """ - # deprecated in 0.14 - warnings.warn("Function is unused by library code. If you use this code, " - "please open an issue in " - "https://github.com/warner/python-ecdsa", - DeprecationWarning) - - return order_mod(x, largest_factor_relatively_prime(m, x)) - - -def is_prime(n): - """Return True if x is prime, False otherwise. - - We use the Miller-Rabin test, as given in Menezes et al. p. 138. - This test is not exact: there are composite values n for which - it returns True. - - In testing the odd numbers from 10000001 to 19999999, - about 66 composites got past the first test, - 5 got past the second test, and none got past the third. - Since factors of 2, 3, 5, 7, and 11 were detected during - preliminary screening, the number of numbers tested by - Miller-Rabin was (19999999 - 10000001)*(2/3)*(4/5)*(6/7) - = 4.57 million. - """ - - # (This is used to study the risk of false positives:) - global miller_rabin_test_count - - miller_rabin_test_count = 0 - - if n <= smallprimes[-1]: - if n in smallprimes: - return True - else: - return False - - if gcd(n, 2 * 3 * 5 * 7 * 11) != 1: - return False - - # Choose a number of iterations sufficient to reduce the - # probability of accepting a composite below 2**-80 - # (from Menezes et al. Table 4.4): - - t = 40 - n_bits = 1 + int(math.log(n, 2)) - for k, tt in ((100, 27), - (150, 18), - (200, 15), - (250, 12), - (300, 9), - (350, 8), - (400, 7), - (450, 6), - (550, 5), - (650, 4), - (850, 3), - (1300, 2), - ): - if n_bits < k: - break - t = tt - - # Run the test t times: - - s = 0 - r = n - 1 - while (r % 2) == 0: - s = s + 1 - r = r // 2 - for i in xrange(t): - a = smallprimes[i] - y = pow(a, r, n) - if y != 1 and y != n - 1: - j = 1 - while j <= s - 1 and y != n - 1: - y = pow(y, 2, n) - if y == 1: - miller_rabin_test_count = i + 1 - return False - j = j + 1 - if y != n - 1: - miller_rabin_test_count = i + 1 - return False - return True - - -def next_prime(starting_value): - "Return the smallest prime larger than the starting value." - - if starting_value < 2: - return 2 - result = (starting_value + 1) | 1 - while not is_prime(result): - result = result + 2 - return result - - -smallprimes = [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, 547, 557, 563, 569, 571, - 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, - 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, - 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, - 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, - 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, - 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, - 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, - 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, - 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, - 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229] - -miller_rabin_test_count = 0 -- cgit v1.2.3