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 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 for k rounds of the test, applied to uniformly random . The same bound also applies to the related problem of what is the conditional probability of n being composite for a random number which has been declared prime in k rounds of the test. Complexity The Solovay–Strassen algorithm shows that the decision problem COMPOSITE is in the complexity class RP. References Further reading See also External links Solovay-Strassen Implementation of the Solovay–Strassen primality test in Maple Primality tests Modular arithmetic Randomized algorithms