'I am trying to write a function in Python encapsulating the Miller-Rabin primality test, but it is very slow
Here is my code:
import random
def miller(n, k):
"""
takes an integer n and evaluates whether it is a prime or a composite
n > 3, odd integer to be tested for primality
k, rounds of testing (the more tests, the more accurate the result)
"""
temp = n - 1 # used to find r and d in n = 2**d * r + 1, hence temporary
r = 0
while True:
if temp / 2 == type(int):
r += 1
else:
d = temp
break
temp = temp / 2
for _ in range(k):
a = random.SystemRandom().randrange(2, n - 2)
x = a**d % n
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = x**2 % n
if x == n - 1:
continue
return "Composite"
return "Probably prime"
Certainly there must be more effective ways to implement the algorithm in Python, so that it may handle large integers with ease?
Cheers
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
