I am trying to write a function in Python encapsulating the Miller-Rabin primality test, but it is very slow

118 Views Asked by At

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

0

There are 0 best solutions below