this script implements the solovaystrassen primality test this probabilistic primality test is based on euler s criterion it is similar to the fermat test but uses quadratic residues it can quickly identify composite numbers but may occasionally classify composite numbers as prime more details and concepts about this can be found on https en wikipedia orgwikisolovaye28093strassenprimalitytest calculate the jacobi symbol the jacobi symbol is a generalization of the legendre symbol which can be used to simplify computations involving quadratic residues the jacobi symbol is used in primality tests like the solovaystrassen test because it helps determine if an integer is a quadratic residue modulo a given modulus providing valuable information about the number s potential primality or compositeness parameters randoma a randomly chosen integer from 2 to n2 inclusive number the number that is tested for primality returns jacobisymbol the jacobi symbol is a mathematical function used to determine whether an integer is a quadratic residue modulo another integer usually prime or not jacobisymbol2 13 1 jacobisymbol5 19 1 jacobisymbol7 14 0 check whether the input number is prime or not using the solovaystrassen primality test parameters number the number that is tested for primality iterations the number of times that the test is run which effects the accuracy returns result true if number is probably prime and false if not random seed10 solovaystrassen13 5 true solovaystrassen9 10 false solovaystrassen17 15 true calculate the jacobi symbol the jacobi symbol is a generalization of the legendre symbol which can be used to simplify computations involving quadratic residues the jacobi symbol is used in primality tests like the solovay strassen test because it helps determine if an integer is a quadratic residue modulo a given modulus providing valuable information about the number s potential primality or compositeness parameters random_a a randomly chosen integer from 2 to n 2 inclusive number the number that is tested for primality returns jacobi_symbol the jacobi symbol is a mathematical function used to determine whether an integer is a quadratic residue modulo another integer usually prime or not jacobi_symbol 2 13 1 jacobi_symbol 5 19 1 jacobi_symbol 7 14 0 check whether the input number is prime or not using the solovay strassen primality test parameters number the number that is tested for primality iterations the number of times that the test is run which effects the accuracy returns result true if number is probably prime and false if not random seed 10 solovay_strassen 13 5 true solovay_strassen 9 10 false solovay_strassen 17 15 true
import random


def jacobi_symbol(random_a: int, number: int) -> int:
    

    if random_a in (0, 1):
        return random_a

    random_a %= number
    t = 1

    while random_a != 0:
        while random_a % 2 == 0:
            random_a //= 2
            r = number % 8
            if r in (3, 5):
                t = -t

        random_a, number = number, random_a

        if random_a % 4 == number % 4 == 3:
            t = -t

        random_a %= number

    return t if number == 1 else 0


def solovay_strassen(number: int, iterations: int) -> bool:
    

    if number <= 1:
        return False
    if number <= 3:
        return True

    for _ in range(iterations):
        a = random.randint(2, number - 2)
        x = jacobi_symbol(a, number)
        y = pow(a, (number - 1) // 2, number)

        if x == 0 or y != x % number:
            return False

    return True


if __name__ == "__main__":
    import doctest

    doctest.testmod()