Evaluation and comparison of two efficient probabilistic primality testing algorithms

We analyse two recent probabilistic primality testing algorithms; the first one is derived from Miller 6] in a formulation given by Rabin 7], and the second one is from Solovay and Strassen 9]. Both decide whether or not an odd number n is prime in time O(m, lognM(n)) with an error probability less than α^m, for some $\text{0≤a<}\text{1}\text{2}$. Our comparison shows that the first algorithm is always more efficient than the second, both in probabilistic and algorithmic terms.