# 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