LCS Publication Details
Publication Title: AN ANALYSIS OF THE SOLOVAY AND STRASSEN TEST FOR PRIMALITY
Publication Author: Baratz, Alan E.
Additional Authors:
LCS Document Number: MIT-LCS-TM-108
Publication Date: 7-1-1978
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
In this paper we will analyze the performance of the Solovay and Strassen 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 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).
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.