maths.solovay_strassen_primality_test¶
This script implements the Solovay-Strassen 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.org/wiki/Solovay%E2%80%93Strassen_primality_test
Functions¶
|
Calculate the Jacobi symbol. The Jacobi symbol is a generalization |
|
Check whether the input number is prime or not using |
Module Contents¶
- maths.solovay_strassen_primality_test.jacobi_symbol(random_a: int, number: int) int¶
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
- maths.solovay_strassen_primality_test.solovay_strassen(number: int, iterations: int) bool¶
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