'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