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<a<n}$ ${\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<b<n-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 {ggT} (29,91)=1,\,\,b=29^{45}\equiv 1({\text{mod }}\,91),\,\,J(29,91)=1\equiv b{\text{ mod }}91\implies {\text{ Primzahl nicht ausgeschlossen }}}$

Test 2: ${\displaystyle a=17}$

${\displaystyle g=\operatorname {ggT} (17,91)=1,\,\,b=17^{45}\equiv -1({\text{mod }}\,91),\,\,J(17,91)=-1\equiv b{\text{ mod }}91\implies {\text{Primzahl nicht ausgeschlossen}}}$

Test 3: ${\displaystyle a=23}$

${\displaystyle g=\operatorname {ggT} (23,91)=1,\,\,b=23^{45}\equiv 64({\text{mod }}\,91)\implies {\text{keine Primzahl}}}$

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)<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