Remove Solovay-Strassen implementation

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