This is the Prime Pages'
interface to our BibTeX database. Rather than being an exhaustive database,
it just lists the references we cite on these pages. Please let me know of any errors you notice.|
References: [ Home | Author index | Key index | Search ]
- R. Burthe, Jr., "Further investigations with the strong probable prime test," Math. Comp., 65:213 (1996) 373--381. MR 96d:11137
Recently, Damgård, Landrock and Pomerance described a procedure in which a k-bit odd number is chosen at random and subjected to t random strong probable prime tests. If the chosen number passes all t tests, then the procedure will return that number; otherwise, another k-bit odd integer is selected and then tested. The procedure ends when a number that passes all t tests is found. Let pk,t denote the probability that such a number is composite. The authors above have shown that pk,t≤ 4-t when k≥ 51 and t≥ 1. In this paper we will show that this is in fact valid for all k≥ 2 and t≥ 1.