# 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. ${\ displaystyle n}$ ${\ displaystyle a}$ ${\ displaystyle 1 ${\ displaystyle a}$ • 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.${\ displaystyle g: = \ operatorname {ggT} (a, n)}$ ${\ displaystyle g> 1}$ ${\ displaystyle g}$ ${\ displaystyle n}$ ${\ displaystyle n}$ • Calculate
${\ displaystyle b: = a ^ {\ frac {n-1} {2}} \ mod n}$ 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.${\ displaystyle 1 ${\ displaystyle n}$ ${\ displaystyle b = 1}$ ${\ displaystyle b = n-1}$ ${\ displaystyle n}$ • 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.${\ displaystyle J (a, n)}$ ${\ displaystyle n}$ ${\ displaystyle J (a, n) \ equiv b \ mod \ n}$ ${\ displaystyle n}$ • If the calculations are consecutive or result, the Solovay-Strassen test does not provide any information, so it may be a prime number.${\ displaystyle g = 1, b = 1}$ ${\ displaystyle b = n-1, J (a, n) \ equiv b \ mod \ n}$ ${\ displaystyle n}$ ## 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. ${\ displaystyle n}$ • If is a prime number, the test always gives the correct result (namely “no statement”).${\ displaystyle n}$ • 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 ).${\ displaystyle n}$ ${\ displaystyle a}$ 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. ${\ displaystyle a}$ ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle n}$ ${\ displaystyle 1/2 ^ {k}}$ ## 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: ${\ displaystyle n = 91}$ Is 91 a Prime Number?

Test 1:${\ displaystyle a = 29}$ ${\ displaystyle g = \ operatorname {gcd} (29.91) = 1, \, \, b = 29 ^ {45} \ equiv 1 ({\ text {mod}} \, 91), \, \, J (29.91) = 1 \ equiv b {\ text {mod}} 91 \ implies {\ text {prime number not excluded}}}$ Test 2: ${\ displaystyle a = 17}$ ${\ displaystyle g = \ operatorname {gcd} (17.91) = 1, \, \, b = 17 ^ {45} \ equiv -1 ({\ text {mod}} \, 91), \, \, J (17,91) = - 1 \ equiv b {\ text {mod}} 91 \ implies {\ text {prime number not excluded}}}$ Test 3: ${\ displaystyle a = 23}$ ${\ displaystyle g = \ operatorname {ggT} (23.91) = 1, \, \, b = 23 ^ {45} \ equiv 64 ({\ text {mod}} \, 91) \ implies {\ text { no prime number}}}$ ## 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 ${\ displaystyle n}$ ${\ displaystyle a}$ ${\ displaystyle n}$ ${\ displaystyle a ^ {\ frac {n-1} {2}} \ equiv J (a, n) \ mod n}$ .

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 . ${\ displaystyle n = 91}$ ${\ displaystyle a = 17.29}$ ${\ displaystyle (\ mathbb {Z} / n) ^ {*}}$ ${\ displaystyle {\ frac {\ varphi (n)} {2}}}$ ${\ displaystyle \ varphi}$ ${\ displaystyle n}$ ${\ displaystyle \ varphi (n) ${\ displaystyle a}$ ${\ displaystyle k}$ ${\ displaystyle 1/2 ^ {k}}$ ## 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

${\ displaystyle a ^ {\ frac {p-1} {2}} \ equiv \ pm 1 \ mod p}$ .

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

${\ displaystyle a ^ {\ frac {p-1} {2}} \ equiv {\ Big (} {\ frac {a} {p}} {\ Big)} \ mod p}$ .

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