An Analysis of the Solovay and Strassen Test for Primality

Abstract

In this paper we will analyze the performace of the Solovay and Strasses probabilistic primality testing algorithm. We will show that iterating Solovay and Strassen's algorithm r times using independent random numbers at each iteration, results in a test for the primality of any positive odd integer, n>2, with error probability of 0 (if n is prime), error probability at most 4^-r (if n is composite and non-Carmichael), and error probability at most 2^-r (if n is composite and Carmichael).