# Commits

committed 36f28ee

edited iscond2

• Participants
• Parent commits 226143f

# File #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`

# File miller_rabin.py

` `
` 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`
` `