This is a python function that uses the Miller test to determine if a given number is prime or not. The function is deterministic and it checks if the given number is 2 or 3, less than 2, even, a multiple of 3, or less than 9. If the number satisfies any of these conditions, the function returns False. If not, the function uses the Miller test t…

miller_test.py

import math


def miller_test(n: int) -> bool:
    """
    Check if a number is a prime (Miller Test). This algorithm is deterministic.

    :param n: integer to check
    :return: True if n is a prime, False otherwise
    """
    # Check if n is equal to 2 or 3
    if n == 2 or n == 3:
        return True

    # Check if n is less than 2 or is even or is a multiple of 3
    if n < 2 or not n & 1 or not n % 3:
        return False

    # Check if n is less than 9
    if n < 9:
        return True

    # Check if n is prime using the Miller test
    for a in range(2, min(n - 2, int(2 * math.log(n) ** 2)) + 1):
        def miller_rabin():
            # Calculate the exponent of n - 1
            exp = n - 1
            while not exp & 1:
                exp >>= 1

            # Compute the power of a mod n
            x = pow(a, exp, n)
            if x == 1 or x == n - 1:
                return True

            # Check if n is prime
            while exp < n - 1:
                if pow(a, exp, n) == n - 1:
                    return True
                exp <<= 1
            return False

        # Return False if n is not prime
        if not miller_rabin():
            return False
    # Return True if n is prime
    return True