Let \(n\) be odd and write \(n-1= 2^ s u\), where \(u\) is odd. If \(n\) is a prime and \(n\nmid a\), then either \(a^ u\equiv 1\pmod n\) or \(a^{2^ i u}\equiv -1\pmod n\) for some \(i<s\). If this holds for some pair \(n\), \(a\), where \(n\) is not necessarily a prime, we say that \(n\) is a strong probable prime. Suppose \(n\) is selected randomly from the set \(M_ k\) of odd \(k\)-bit integers. We continue to choose numbers \(n\) from \(M_ k\) until we find one that passes \(t\) random strong probable prime tests. Let \(p_{k,t}\) denote the probability that this procedure returns a composite \(n\). The authors obtain numerical upper bounds for \(p_{k,t}\) for various choices of \(k\), \(t\); in particular, \(p_{100,10}< 2^{- 44}\), \(p_{300,5}< 2^{-60}\), and \(p_{k,1}\leq k^ 2 4^{2- \sqrt{k}}\) for all \(k\geq 2\).