| dc.description.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). | en_US |
