Benchmark for an implementation of the Miller-Rabin-Primetest

34 Views Asked by At

I have an implementation of the Miller-Rabin-Primetest, coded in python3. Unfortunately I have no idea how "fast" this test should be on my machine. With my code I can test the number $n = 2^{10^4}+1$ in less than 4 seconds. But I don't know whether this is a good time. Can I get a kind of a benchmark? Here is my code:

def rab_test(N, rounds = 40):
    if N in [2, 3]:
        return True
    if N % 2 == 0:
        return False
    n = N // 2
    t = 1
    while n % 2 == 0:
        n = n // 2
        t += 1
    a = random.randrange(2, N-1)
    u = gmpy2.powmod(a, n, N)
    if u == 1 or N-u == 1:
        return True
    for k in range(1, t):
        u = gmpy2.powmod(u, 2, N)
        if N-u == 1:
            return True
    return False    
0

There are 0 best solutions below