Further investigations with the strong probable prime test
HTML articles powered by AMS MathViewer
- by Ronald Joseph Burthe Jr. PDF
- Math. Comp. 65 (1996), 373-381 Request permission
Abstract:
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 $p_{k,t}$ denote the probability that such a number is composite. The authors above have shown that $p_{k,t}\le 4^{-t}$ when $k\ge 51$ and $t\ge 1$. In this paper we will show that this is in fact valid for all $k\ge 2$ and $t\ge 1$.References
- Pierre Beauchemin, Gilles Brassard, Claude Crépeau, and Claude Goutier, Two observations on probabilistic primality testing, Advances in cryptology—CRYPTO ’86 (Santa Barbara, Calif., 1986) Lecture Notes in Comput. Sci., vol. 263, Springer, Berlin, 1987, pp. 443–450. MR 907106, DOI 10.1007/3-540-47721-7_{3}2
- Pierre Beauchemin, Gilles Brassard, Claude Crépeau, Claude Goutier, and Carl Pomerance, The generation of random numbers that are probably prime, J. Cryptology 1 (1988), no. 1, 53–64. MR 935901, DOI 10.1007/BF00206325
- Ivan Damgård, Peter Landrock, and Carl Pomerance, Average case error estimates for the strong probable prime test, Math. Comp. 61 (1993), no. 203, 177–194. MR 1189518, DOI 10.1090/S0025-5718-1993-1189518-9
- Louis Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12 (1980), no. 1, 97–108. MR 582244, DOI 10.1016/0304-3975(80)90007-9
- Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI 10.1016/0022-314X(80)90084-0
Additional Information
- Ronald Joseph Burthe Jr.
- Email: ronnie@alpha.math.uga.edu
- Received by editor(s): May 3, 1994
- © Copyright 1996 American Mathematical Society
- Journal: Math. Comp. 65 (1996), 373-381
- MSC (1991): Primary 11Y11; Secondary 11A51
- DOI: https://doi.org/10.1090/S0025-5718-96-00695-3
- MathSciNet review: 1325864