Solovay Strassen test

from Wikipedia, the free encyclopedia

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” .


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.


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.


The Solovay-Strassen test is efficient because the GCD, the powers and the Jacobi symbol can be calculated efficiently.


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.


  • Paulo Ribenboim : The world of prime numbers , Springer Verlag, 1996, p. 97