Solovay-Strassen Primeabilty Test
[Primes Home][Home]
Prime numbers are important with encryption, and often used within public key encryption. It is thus important to generate numbers that can be tested for the primeality. One method is the Solovay–Strassen primality test [2], and will determine is a number is probably a prime number. Normally these days we use the Miller-Rabin method, but it is still valid. Overall it uses the Euler–Jacobi pseudo-prime test and where the Euler test is \(a^{n-1} \equiv 1 \pmod n\) and the Jacobi test is \(a^\frac{n-1}{2} \equiv \left(\frac{a}{n}\right) \pmod n\), and where \(\left(\frac{a}{n}\right) \) is the Jacobi symbol. The result we get shows that a number is probably prime, as Carmichael numbers [here][1] (such as 561 and 1729) pass the test, even though they are composite numbers.
|
Prime numbers are important with encryption, and often used within public key encryption. It is thus important to generate numbers that can be tested for the primeality. One method is the Solovay–Strassen primality test, and will determine is a number is probably a prime number. Normally these days we use the Miller-Rabin method, but it is still valid. Overall it uses the Euler–Jacobi pseudo-prime test and where the Euler test is:
\(a^{n-1} \equiv 1 \pmod n\)
and the Jacobi test is:
\(a^\frac{n-1}{2} \equiv \left(\frac{a}{n}\right) \pmod n\)
and where \(\left(\frac{a}{n}\right)\) is the Jacobi symbol. The result we get shows that a number is probably prime, as Carmichael numbers (such as 561 and 1729) pass the test, even though they are composite numbers. An outline of the code is:
import sys import libnum a=2 n=561 def legendre_symbol(a, p): # Returns 1 if a has a square root modulo p, -1 otherwise. ls = pow(a, (p - 1) // 2, p) return -1 if ls == p - 1 else ls if (len(sys.argv)>1): n=int(sys.argv[1]) if (len(sys.argv)>2): a=int(sys.argv[2]) print ("a = ",a) print ("n = ",n) if (libnum.gcd(a,n)!=1): print ("a and n share a factor"); sys.exit() val=pow(a,(n-1)//2, n) val2=pow(a,n-1, n) leg=legendre_symbol(a,n) print (f"Euler test: {a}^({n-1}) (mod {n}) = {val2}") print (f"Jacobi test: {a}^({(n-1)//2}) (mod {n}) = {val}") print (f"Legendre symbol = {leg}") if (val==(n-1)): val=-1 if (val==leg and val2==1): print (f"\n{n} is probably prime") else: print (f"\n{n} is not prime")
A sample run with an unsafe value is:
a = 5 n = 162259276829213363391578010288127 Euler test: 5^(162259276829213363391578010288126) (mod 162259276829213363391578010288127) = 1 Jacobi test: 5^(81129638414606681695789005144063) (mod 162259276829213363391578010288127) = 162259276829213363391578010288126 Legendre symbol = -1 162259276829213363391578010288127 is probably prime
[1] Carmichael, R. D. (1910). Note on a new number theory function. Bulletin of the American Mathematical Society, 16(5), 232–238.
[2] Solovay, R., & Strassen, V. (1977). A fast Monte-Carlo test for primality. SIAM journal on Computing, 6(1), 84–85.