Editing Solovay–Strassen primality test (section)

==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.