Memory Error in Python Primality Testing program

Question

def repeated(m, result, a, s, d):

check = True
r = 0
while r <= s - 1:
    if result == m - 1:
        check = False
        return check
    result = (result ** 2) % m
    r = r + 1
return check

I need to write a primality testing python program to test very large numbers, like at least 100-digit numbers. The code above is part of the code for Miller Rabin deterministic primality test for repeated squaring. It works really slow for large numbers. How can I speed it up? It is for a project. Thanks!

Answer 1

your problem is probably the (result ** 2) % m, use the 3 argument version of pow that do the same but more efficiently because the algorithm use is the Modular exponentiation and that is much better than first doing x**n and then calculate its modulo. this way you are guaranty to never have a number bigger than m while if you do (x**n) % m you can have that x**n is very much bigger than m that may be the cause your problems

Also no need for the check variable and you don't use a. Also as you go from 0 to s-1, better use range

def repeated(m, result, s, d):
    for r in range(s):
        if result == m - 1:
            return False
        result = pow(result, 2, m )
    return True

Now for this part of the test

if

you need a, d, s, and n this is how I would do it

def mr_check(n,a,s,d):
    result = pow(a,d,n)
    if result == 1 :
        return False
    for r in range(s):
        result = pow(result,2,n)
        if result == n-1:
            return False
    return True