Editing Solovay–Strassen primality test (section)

==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]] 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 [[Elliptic curve primality proving|ECPP]] or the [[Pocklington primality test]]<ref>[http://mathworld.wolfram.com/PocklingtonsTheorem.html Pocklington test on Mathworld]</ref> should be used which ''proves'' primality.