elementary primality testing algos

prime_testing.py

from random import randint
import logging
from codetiming import Timer

logging.basicConfig(level=logging.DEBUG)
# Primality testing script for miller rabin & fermat tests
# https://crypto.stanford.edu/pbc/notes/numbertheory/millerrabin.html
# https://cp-algorithms.com/algebra/primality_tests.html
def probablyPrimeFermat(N, tries=5):
    if N < 4:
        return N == 2 or N == 3
    logging.debug(f"Testing fermat prime of {N}")
    # pick random base a to check Fermat's theorem
    for t in range(tries):
        base = randint(2, N-2)
        logging.debug(f"Base is {base}...")
        if pow(base, N-1, N) != 1:
            return False

    return True


def checkCompositeness(base, N, d, r):
    ''' compute powers 2^r*d modulo N  to check compositeness'''
    facts = pow(base, d, N)
    # >= 75% chance that composite N will fail all tests
    logging.debug(f"Testing {base}**{d} mod {N} = {facts}...")
    if facts == 1 or facts == N - 1:
        return False
    while r > 0:
        facts = (facts * facts) % N
        r -= 1
        d *= 2
        logging.debug(f"Testing {base}**{d} mod {N} = {facts}...")
        if facts == N-1:
            return False
    return True



def probablyPrimeMillerRabin(N, tries=5):
    if N < 4:
        return N == 2 or N == 3
    logging.debug(f"Testing Miller Rabin probable prime or composite - {N}")

    r = 0
    d = N -1
    while d & 1 == 0:
        d >>= 1
        r+=1
    # computing N- 1 = 2^r*d

    # pick random base a and test a^
    for t in range(tries):
        base = randint(2, N-2)
        logging.debug(f"Base is {base}...")
        if checkCompositeness(base, N, d, r):
            return False

    return True


def executePrimeTests(primelist, notprimelist, primetestfunc, iterations):
    for i in isprimelist:
        print(primetestfunc(i, iterations))

    for j in isnotprimelist:
        print(not primetestfunc(j, iterations))

if __name__ == "__main__":
    isprimelist = [179424673, 20678048681, 1162566711635022452267983]
    isnotprimelist = [2931, 2152302898747, 877777777777777777777777]

    with Timer(text="Fermat Test completed in {:.8f} seconds"):
        executePrimeTests(isprimelist, isnotprimelist, probablyPrimeFermat, 5)

    with Timer(text="Miller Rabin Test completed in {:.8f} seconds"):
        executePrimeTests(isprimelist, isnotprimelist, probablyPrimeMillerRabin, 5)