Commits

Anonymous committed 36f28ee

edited iscond2

Comments (0)

Files changed (2)

#miller_rabin.py#

+from math import log, pow
+
+# two conditions
+# if a number meets one of them, it's likely a prime number.
+# otherwise it's a composite number.
+def iscond1(b, k, n):
+    if ((pow(b, k)) % n == 1):
+        return True
+    return False
+
+def iscond2(b, k, n, q):
+    for i in range(0, int(q)):
+        if ((pow(b, (k * pow(2, i))) + 1) % n == 0):
+            return True
+    return False
+
+# isprime(n) tests whether the n is a prime number using the Miller-Rabin primality test.
+# input: an integer
+# output: Boolean
+def isprime(n):
+    b = 3 # b is a random number between 0 and n-1
+    k = 1
+    while (k <= (n - 1)):
+        q = log(((n - 1) / k), 2)
+        if ((q % 1 == 0) and
+            (iscond1(b, k, n)) or
+            (iscond2(b, k, n, q))):
+            print n, "is probably a prime number.\n"
+            return True
+        k += 2
+    print n, "is not a prime number.\n"
+    return False
 
 def iscond2(b, k, n, q):
     for i in range(0, int(q)):
-        if ((pow(b, (k * pow(2, i))) + 1) % n == 0):
+        if ((pow(b, (k * pow(2, i)))) % n == (n - 1)):
             return True
     return False