diff options
Diffstat (limited to 'rsa/prime.py')
-rw-r--r-- | rsa/prime.py | 63 |
1 files changed, 0 insertions, 63 deletions
diff --git a/rsa/prime.py b/rsa/prime.py index d8fd6e0..c377c91 100644 --- a/rsa/prime.py +++ b/rsa/prime.py @@ -37,69 +37,6 @@ def gcd(p, q): return p -def jacobi(a, b): - """Calculates the value of the Jacobi symbol (a/b) where both a and b are - positive integers, and b is odd - - :returns: -1, 0 or 1 - """ - - assert a > 0 - assert b > 0 - - result = 1 - while a > 1: - if a & 1: - if ((a - 1) * (b - 1) >> 2) & 1: - result = -result - a, b = b % a, a - else: - if (((b * b) - 1) >> 3) & 1: - result = -result - a >>= 1 - if a == 0: - return 0 - return result - - -def jacobi_witness(x, n): - """Returns False if n is an Euler pseudo-prime with base x, and True otherwise.""" - - j = jacobi(x, n) % n - - f = pow(x, n >> 1, n) - - if j == f: - return False - return True - - -def randomized_primality_testing(n, k): - """Calculates whether n is composite (which is always correct) or - prime (which is incorrect with error probability 2**-k) - - Returns False if the number is composite, and True if it's - probably prime. - """ - - # 50% of Jacobi-witnesses can report compositness of non-prime numbers - - # The implemented algorithm using the Jacobi witness function has error - # probability q <= 0.5, according to Goodrich et. al - # - # q = 0.5 - # t = int(math.ceil(k / log(1 / q, 2))) - # So t = k / log(2, 2) = k / 1 = k - # this means we can use range(k) rather than range(t) - - for _ in range(k): - x = rsa.randnum.randint(n - 1) - if jacobi_witness(x, n): - return False - - return True - - def miller_rabin_primality_testing(n, k): """Calculates whether n is composite (which is always correct) or prime (which theoretically is incorrect with error probability 4**-k), by |