diff options
Diffstat (limited to 'frozen_deps/ecdsa/numbertheory.py')
| -rw-r--r-- | frozen_deps/ecdsa/numbertheory.py | 30 |
1 files changed, 20 insertions, 10 deletions
diff --git a/frozen_deps/ecdsa/numbertheory.py b/frozen_deps/ecdsa/numbertheory.py index d3500c7..fe974f8 100644 --- a/frozen_deps/ecdsa/numbertheory.py +++ b/frozen_deps/ecdsa/numbertheory.py @@ -20,11 +20,11 @@ try: except NameError: xrange = range try: - from gmpy2 import powmod + from gmpy2 import powmod, mpz GMPY2 = True GMPY = False -except ImportError: +except ImportError: # pragma: no branch GMPY2 = False try: from gmpy import mpz @@ -33,8 +33,15 @@ except ImportError: except ImportError: GMPY = False + +if GMPY2 or GMPY: # pragma: no branch + integer_types = tuple(integer_types + (type(mpz(1)),)) + + import math import warnings +import random +from .util import bit_length class Error(Exception): @@ -216,14 +223,15 @@ def square_root_mod_prime(a, p): range_top = min(0x7FFFFFFF, p) else: range_top = p - for b in xrange(2, range_top): + for b in xrange(2, range_top): # pragma: no branch if jacobi(b * b - 4 * a, p) == -1: f = (a, -b, 1) ff = polynomial_exp_mod((0, 1), (p + 1) // 2, f, p) if ff[1]: raise SquareRootError("p is not prime") return ff[0] - raise RuntimeError("No b found.") + # just an assertion + raise RuntimeError("No b found.") # pragma: no cover # because all the inverse_mod code is arch/environment specific, and coveralls @@ -346,7 +354,7 @@ def factorization(n): q, r = divmod(n, d) if r == 0: count = 1 - while d <= n: + while d <= n: # pragma: no branch n = q q, r = divmod(n, d) if r != 0: @@ -370,7 +378,8 @@ def factorization(n): if r == 0: # d divides n. How many times? count = 1 n = q - while d <= n: # As long as d might still divide n, + # As long as d might still divide n, + while d <= n: # pragma: no branch q, r = divmod(n, d) # see if it does. if r != 0: break @@ -555,8 +564,8 @@ def is_prime(n): return True else: return False - - if gcd(n, 2 * 3 * 5 * 7 * 11) != 1: + # 2310 = 2 * 3 * 5 * 7 * 11 + if gcd(n, 2310) != 1: return False # Choose a number of iterations sufficient to reduce the @@ -564,7 +573,8 @@ def is_prime(n): # (from Menezes et al. Table 4.4): t = 40 - n_bits = 1 + int(math.log(n, 2)) + n_bits = 1 + bit_length(n) + assert 11 <= n_bits <= 16384 for k, tt in ( (100, 27), (150, 18), @@ -591,7 +601,7 @@ def is_prime(n): s = s + 1 r = r // 2 for i in xrange(t): - a = smallprimes[i] + a = random.choice(smallprimes) y = pow(a, r, n) if y != 1 and y != n - 1: j = 1 |