Solovay Strassen test
The Solovay-Strassen test (according to Robert M. Solovay and Volker Strassen ) is a probabilistic prime number test . The test checks for an odd number n whether it is prime or composite . In the latter case, however, the test generally does not yield a factor of the number n .
Like the Miller-Rabin test , the Solovay-Strassen test is a Monte Carlo algorithm . This means that it only delivers a statement with a certain probability (50%). However, this probability can be increased at will through repetition. If the test (repeatedly) does not produce a statement, this can be interpreted as “n is probably a prime number” .
method
For an odd number , which is tested on prime property, a natural number is randomly with selected. If the test is carried out several times , new values must be selected for each time.
- The greatest common factor is calculated. If true, then is a proper divisor of . This is not a prime number and the test is ended.
- Calculate
- If so, then according to Euler's theorem there can not be a prime and the test is ended. But if or , it can be an Euler's pseudoprime number and the following step has to be carried out.
- Calculate the Jacobi symbol . If is a prime number, then it must hold. If this is not the case, the number can not be prime and the test is ended.
- If the calculations are consecutive or result, the Solovay-Strassen test does not provide any information, so it may be a prime number.
rating
In order to evaluate the quality of the Solovay-Strassen test, a distinction must be made between whether it is a prime number or not.
- If is a prime number, the test always gives the correct result (namely “no statement”).
- If it is not a prime number, the probability of choosing one in the first step of the test so that the test gives a false result is less than 1/2 (see below: False witnesses ).
In order to increase the quality of the test for non-prime numbers, the test is repeated a sufficient number of times with independently chosen random bases . If the test is repeated several times, then the probability that the result is “no statement” in all of the repetitions (although it is not a prime number) is less than . This is a pessimistic estimate - in most cases the goodness will be much better.
Efficiency
The Solovay-Strassen test is efficient because the GCD, the powers and the Jacobi symbol can be calculated efficiently.
example
Using the example of the composite number (a Fermat pseudoprime number to - for example - bases 17, 29), a possible sequence of the test is shown:
Is 91 a Prime Number?
Test 1:
Test 2:
Test 3:
False witnesses
Let n> 2 be an odd composite number.
A number that is too prime is called a false witness for the primality of with regard to the Solovay-Strassen test, if
- .
For then, are the bases false witnesses. Since the set of false witnesses forms a subgroup of the multiplicative group with order less than or equal to ( the Euler's φ function , which specifies the number of coprime numbers less than ) and applies, at most half of all the available bases are false witnesses . Therefore, one reaches a probability of an error (i.e., a composite number is not recognized as such) that is smaller than .
What is behind the Solovay Strassen test?
The Solovay-Strassen test is based on two prime number properties:
One is Euler's theorem : For every prime number p > 2 applies
- .
With this criterion, all numbers are filtered out that are neither prime numbers nor Euler's pseudoprimes with base a .
The other property connects this with the Legendre symbol : For every prime number p > 2 applies
- .
Since the numbers to be tested cannot be assumed to be prime numbers, the Jacobi symbol is used .
With this criterion, the Euler-Jacobi pseudoprimes also drop out.
literature
- Paulo Ribenboim : The world of prime numbers , Springer Verlag, 1996, p. 97