Skip to content

Instantly share code, notes, and snippets.



Created Jun 28, 2013
What would you like to do?
Python implementation of the Fermat Primality Test
def fermat_test(n, k):
# Implementation uses the Fermat Primality Test
# If number is even, it's a composite number
if n == 2:
return True
if n % 2 == 0:
return False
for i in xrange(k):
a = random.randint(1, n-1)
if pow(a, n-1) % n != 1:
return False
return True

This comment has been minimized.

Copy link

@bm777 bm777 commented Mar 16, 2021

Waouh, that is cool.
Did you found a prime number using this method? like a prime number with 10^3 digit?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment