View source for Solovay–Strassen primality test

The '''Solovay–Strassen [[Primality test|primality test]]''', developed by [[Biography:Robert M. Solovay|Robert M. Solovay]] and [[Biography:Volker Strassen|Volker Strassen]] in 1977, is a [[Randomized algorithm|probabilistic]] test to determine if a number is [[Composite number|composite]] or probably prime. The idea behind the test was discovered by M. M. Artjuhov in 1967<ref>{{citation
 | last = Artjuhov | first = M. M.
 | journal = Acta Arithmetica
 | mr = 0213289
 | pages = 355–364
 | title = Certain criteria for primality of numbers connected with the little Fermat theorem
 | volume = 12
 | year = 1966–1967}}</ref>  
(see Theorem E in the paper). This test has been largely superseded by the Baillie–PSW primality test and the [[Miller–Rabin primality test]], but has great historical importance in showing the practical feasibility of the RSA [[Cryptosystem|cryptosystem]]. The Solovay–Strassen test is essentially an Euler–Jacobi probable prime test.

==Concepts==
[[Biography:Leonhard Euler|Euler]] proved<ref>[[Euler's criterion]]</ref> that for any odd [[Prime number|prime number]] ''p'' and any integer ''a'',

:<math>a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \pmod p </math>

where <math>\left(\tfrac{a}{p}\right)</math> is the [[Legendre symbol]]. The [[Jacobi symbol]] is a generalisation of the Legendre symbol to <math>\left(\tfrac{a}{n}\right)</math>, where ''n'' can be any odd integer. The Jacobi symbol can be computed in time [[Big O notation|O]]((log&nbsp;''n'')²) using Jacobi's generalization of the
[[Quadratic reciprocity|law of quadratic reciprocity]].

Given an odd number ''n'' we can contemplate whether or not the congruence

:<math> a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod n</math>

holds for various values of the "base" ''a'', given that ''a'' is [[Coprime integers|relatively prime]] to ''n''.  If ''n'' is prime then this congruence is true for all ''a''.  So if we pick values of ''a'' at random and test the congruence, then 
as soon as we find an ''a'' which doesn't fit the congruence we know that ''n'' is not prime (but this does not tell us a nontrivial factorization of ''n''). This base ''a'' is called an ''Euler witness'' for ''n''; it is a witness for the compositeness of ''n''. The base ''a'' is called an ''Euler liar'' for ''n'' if the congruence is true while ''n'' is composite.

For every composite odd ''n'', at least half of all bases

:<math>a \in (\mathbb{Z}/n\mathbb{Z})^* </math>

are (Euler) witnesses as the set of Euler liars is a proper subgroup of <math>(\mathbb{Z}/n\mathbb{Z})^*</math>. For example, for <math> n =65</math>, the set of Euler liars has order 8 and <math> = \{1,8,14,18,47,51,57,64\}</math>, and <math>(\mathbb{Z}/n\mathbb{Z})^*</math> has order 48.

This contrasts with the [[Fermat primality test]], for which the proportion of witnesses may be much smaller.  Therefore, there are no (odd) composite ''n'' without many witnesses, unlike the case of [[Carmichael number]]s for Fermat's test.

==Example==
Suppose we wish to determine if ''n''&nbsp;=&nbsp;221 is prime. We write (''n''&minus;1)/2=110.

We randomly select an ''a'' (greater than 1 and smaller than ''n''): 47.
Using an efficient method for raising a number to a power (mod ''n'') such as [[Modular exponentiation#Left-to-right binary method|binary exponentiation]], we compute:
* ''a''<sup>(''n''&minus;1)/2</sup> mod ''n'' &nbsp;=&nbsp; 47<sup>110</sup> mod 221 &nbsp;=&nbsp; &minus;1 mod 221
* <math>(\tfrac{a}{n})</math> mod ''n'' &nbsp;=&nbsp; <math>(\tfrac{47}{221})</math> mod 221 &nbsp;=&nbsp; &minus;1 mod 221.
This gives that, either 221 is prime, or 47 is an Euler liar for 221. We try another random ''a'', this time choosing ''a''&nbsp;=&nbsp;2:
* ''a''<sup>(''n''&minus;1)/2</sup> mod ''n'' &nbsp;=&nbsp; 2<sup>110</sup> mod 221 &nbsp;=&nbsp; 30 mod 221
* <math>(\tfrac{a}{n})</math> mod ''n'' &nbsp;=&nbsp; <math>(\tfrac{2}{221})</math> mod 221 &nbsp;=&nbsp; &minus;1 mod 221.
Hence 2 is an Euler witness for the compositeness of 221, and 47 was in fact an Euler liar. Note that this tells us nothing about the prime factors of 221, which are actually 13 and 17.

==Algorithm and running time==
The algorithm can be written in [[Pseudocode|pseudocode]] as follows:
 '''inputs''': ''n'', a value to test for primality
         ''k'', a parameter that determines the accuracy of the test
 '''output''': ''composite'' if ''n'' is composite, otherwise ''probably prime''
 
 '''repeat''' ''k'' times:
     choose ''a'' randomly in the range [2,''n'' − 1]
     {{nowrap|<math>x \gets \left( \tfrac{a}{n}\right)</math>}}
     '''if''' {{math|1=''x''&nbsp;=&nbsp;0}} '''or''' {{nowrap|<math>a^{(n-1)/2}\not\equiv x\pmod n</math>}} '''then''' 
         '''return''' ''composite''
 '''return''' ''probably prime''

Using fast algorithms for [[Modular exponentiation|modular exponentiation]], the running time of this algorithm is O(''k''·log<sup>3</sup> ''n''), where ''k'' is the number of different values of ''a'' we test.

==Accuracy of the test==
It is possible for the algorithm to return an incorrect answer. If the input ''n'' is indeed prime, then the output will always correctly be ''probably prime''.  However, if the input ''n'' is composite then it is possible for the output to be incorrectly ''probably prime''. The number ''n'' is then called an Euler–Jacobi pseudoprime.

When ''n'' is odd and composite, at least half of all ''a'' with gcd(''a'',''n'')&nbsp;=&nbsp;1 are Euler witnesses. We can prove this as follows: let {''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''m''</sub>} be the Euler liars and ''a'' an Euler witness. Then, for ''i''&nbsp;=&nbsp;1,2,...,''m'':

:<math>(a\cdot a_i)^{(n-1)/2}=a^{(n-1)/2}\cdot a_i^{(n-1)/2}= a^{(n-1)/2}\cdot \left(\frac{a_i}{n}\right) \not\equiv \left(\frac{a}{n}\right)\left(\frac{a_i}{n}\right)\pmod{n}.</math>

Because the following holds:
:<math>\left(\frac{a}{n}\right)\left(\frac{a_i}{n}\right)=\left(\frac{a\cdot a_i}{n}\right),</math>

now we know that

:<math>(a\cdot a_i)^{(n-1)/2}\not\equiv \left(\frac{a\cdot a_i}{n}\right)\pmod{n}.</math>

This gives that each ''a''<sub>''i''</sub> gives a number ''a''·''a''<sub>''i''</sub>, which is also an Euler witness.  
So each Euler liar gives an Euler witness and so the number of Euler witnesses is larger or equal to the number of Euler liars. Therefore, when ''n'' is composite, at least half of all ''a'' with gcd(''a'',''n'')&nbsp;=&nbsp;1 is an Euler witness.

Hence, the probability of failure is at most 2<sup>&minus;''k''</sup> (compare this with the probability of failure for the [[Miller–Rabin primality test]], which is at most 4<sup>&minus;''k''</sup>).

For purposes of [[Cryptography|cryptography]] the more bases ''a'' we test, i.e. if we pick a sufficiently large value of ''k'', the better the accuracy of test. Hence the chance of the algorithm failing in this way is so small that the (pseudo) prime is used in practice in cryptographic applications, but for applications for which it is important to have a prime, a test like ECPP or the Pocklington primality test<ref>[http://mathworld.wolfram.com/PocklingtonsTheorem.html Pocklington test on Mathworld]</ref> should be used which ''proves'' primality.

==Average-case behaviour==
The bound 1/2 on the error probability of a single round of the Solovay–Strassen test holds for any input ''n'', but those numbers ''n'' for which the bound is (approximately) attained are extremely rare. On the average, the error probability of the algorithm is significantly smaller: it is less than

: <math>2^{-k}\exp\left(-(1+o(1))\frac{\log x\,\log\log\log x}{\log\log x}\right)</math>

for ''k'' rounds of the test, applied to uniformly random {{nowrap|''n'' ≤ ''x''}}.<ref>{{cite journal | author=P. Erdős |author2=C. Pomerance  | title=On the number of false witnesses for a composite number | journal=Mathematics of Computation |volume=46 | year=1986 | issue=173 | pages=259–279 | doi=10.2307/2008231 | jstor=2008231}}</ref><ref>{{cite journal | author=I. Damgård |author2=P. Landrock |author3=C. Pomerance  | title=Average case error estimates for the strong probable prime test | journal=Mathematics of Computation | volume=61 | year=1993 | issue=203 | pages=177–194 | doi=10.2307/2152945 | jstor=2152945}}</ref> The same bound also applies to the related problem of what is the conditional probability of ''n'' being composite for a random number {{nowrap|''n'' ≤ ''x''}} which has been declared prime in ''k'' rounds of the test.

==Complexity==
The Solovay&ndash;Strassen algorithm shows that the [[Decision problem|decision problem]] '''COMPOSITE''' is in the [[Complexity class|complexity class]]  '''[[RP (complexity)|RP]]'''.<ref>{{cite book | author=R. Motwani |author2=P. Raghavan  | title=Randomized Algorithms | publisher=Cambridge University Press | year=1995 | isbn=978-0-521-47465-8 | pages=417–423 }}</ref>

==References==
{{Reflist}}

==Further reading==
*{{Cite journal |first1=Robert M. |last1=Solovay |first2=Volker |last2=Strassen |journal=SIAM Journal on Computing |title=A fast Monte-Carlo test for primality |volume=6 |year=1977 |issue=1 |pages=84–85 |doi=10.1137/0206006 }} See also {{Cite journal |first1=Robert M. |last1=Solovay |first2=Volker |last2=Strassen |journal=SIAM Journal on Computing |title=Erratum: A fast Monte-Carlo test for primality |volume=7 |year=1978 |issue=1 |pages=118 |doi=10.1137/0207009 }}
*{{Cite book |last=Dietzfelbinger |first=Martin |chapter=Primality Testing in Polynomial Time, From Randomized Algorithms to "PRIMES Is in P" |title=Lecture Notes in Computer Science |volume=3000 |isbn=978-3-540-40344-9 |date=2004-06-29 |publisher=Springer }}

==External links==
*[https://archive.today/20121220074426/http://computacion.cs.cinvestav.mx/~mruiz/cursos/maestria/csac.html Solovay-Strassen] Implementation of the Solovay–Strassen primality test in Maple

{{number theoretic algorithms}}

{{DEFAULTSORT:Solovay-Strassen Primality Test}}
[[Category:Modular arithmetic]]
[[Category:Randomized algorithms]]

{{Sourceattribution|Solovay–Strassen primality test}}