# Python: Fermat primality test and generating co-primes

There are a number of ways to check if a number is a prime number. Some of these are Probabilistic tests. Like the Fermat primality test.

Using Coprime integers

I wrote this when I working on an example for testing random-based code.

**examples/python/fermat_primality_test/prime.py**

import random import math def get_coprime(n): while True: coprime = random.randrange(n) if math.gcd(coprime, n) == 1: return coprime def fermat_primality(n, count = 1): for _ in range(count): a = get_coprime(n) if (a ** (n-1)) % n != 1: return False return True

**examples/python/fermat_primality_test/test_prime.py**

import prime import random def test_coprime(): random.seed(1) assert prime.get_coprime(10) == 9 assert prime.get_coprime(10) == 1 assert prime.get_coprime(100000) == 64937 def test_fermat_primality(): random.seed(1) assert prime.fermat_primality(1000) == False

Published on 2019-02-18