CODEWITHSUNDEEP
pythonmathprimes
Paris
Paris

Reputation: 105

Fermat primality test too slow - issues with big integers

This is my code for Fermat's primality test:

def fermat(n):
    counter = 0
    prime = False
    if n >= 40:
        upper_bound = 40
    else:
        upper_bound = n - 1

    for a in range(2, upper_bound + 1):
        print(a)
        if pow_mod(a, n - 1, n) == 1:
            counter += 1

    if counter == n - 2 and upper_bound == n - 1 or counter == 39 and upper_bound == 40:
        prime = True

    return prime

pow_mod function calculates a^b mod n with repeated multiplication, applying mod n each time, like this:

def pow_mod(a, b, n):
        result = 1
        for i in range(b):
            result = result * a % n
        return result

It works for relatively small primes. However, if I run it for a large prime such as 67280421310721, it doesn't produce a result in a desirable amount of time. Is it due to the large numbers? How do I fix this?

Upvotes: 0

Views: 249

Answers (1)

superb rain
superb rain

Reputation: 5521

It's because your pow_mod is terribly slow. Use a fast algorithm or just use Python's built-in pow function.

Btw, if I understand your rather convoluted code correctly, you're simply checking whether all tests were successful. Which can be written more clearly:

def fermat(n):
    upper_bound = 40 if n >= 40 else n - 1
    return all(pow(a, n - 1, n) == 1
               for a in range(2, upper_bound + 1))

Upvotes: 4

Related Questions