Further investigations with the strong probable prime test
Ronald Burthe · Mathematics of Computation · 1996
Recently, Damgård, Landrock and Pomerance described a procedure in which a k k -bit odd number is chosen at random and subjected to t t random strong probable prime tests. If the chosen number passes all t t tests, then the procedure will return that number; otherwise, another k k -bit odd integer is selected and then tested. The procedure ends when a number that passes all t t tests is found. Let p k , t p_{k,t} denote the probability that such a number is composite. The authors above have shown that p k , t ≤ 4 − t p_{k,t}\le 4^{-t} when k ≥ 51 k\ge 51 and t ≥ 1 t\ge 1 . In this paper we will show that this is in fact valid for all k ≥ 2 k\ge 2 and t ≥ 1 t\ge 1 .