0

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    
5
  • This would be better asked on the CodeReview exchange. Commented Mar 9, 2024 at 18:38
  • You could compare it against gmpy2.is_prime(N, rounds). It's not quite an apples-to-apples comparison but it will give you an idea if the overhead of going from python to gmpy native code is large. Commented Mar 9, 2024 at 22:28
  • When I repeatedly run rab_test(25) I get False sometimes and True other times. The only change I made to your code was to use generic Python3 pow() instead of gmpy2.powmod(). Is this my error or something amiss in your code? Commented Mar 21, 2024 at 19:19
  • @cdlane I guess it's because they ignore the rounds value and instead do a too small number of rounds. Commented Mar 21, 2024 at 19:27
  • @cdlane Although that's a false positive, falsely returning True. A larger number of rounds would only make that more likely. So I guess they have at least two bugs. Commented Mar 21, 2024 at 19:35

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.