Further investigations

with the strong probable prime test

Author:
Ronald Joseph Burthe Jr.

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

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Recently, Damgård, Landrock and Pomerance described a procedure in which a -bit odd number is chosen at random and subjected to random strong probable prime tests. If the chosen number passes all tests, then the procedure will return that number; otherwise, another -bit odd integer is selected and then tested. The procedure ends when a number that passes all tests is found. Let denote the probability that such a number is composite. The authors above have shown that when and . In this paper we will show that this is in fact valid for all and .

**1**P. Beauchemin, G. Brassard, C. Crépeau, and C. Goutier,*Two observations on probabilistic primality testing*, Advances in Cryptology---Crypto 86 Proceedings (A.M. Odlyzko, ed.), Lecture Notes in Comput. Sci., vol. 263, Springer-Verlag, Berlin, 1987, pp. (443-450), MR**89c:11180**.**2**P. Beauchemin, G. Brassard, C. Crépeau, C. Goutier, and C. Pomerance,*The generation of random numbers that are probably prime, J. Cryptology*, MR**89g:11126**.**3**I. Damgård, P. Landrock, and C. Pomerance,*Average case error estimates for the strong probable prime test*, Math. Comp.**61**(1993), 177--194, MR**94b:11124**.**4**L. Monier,*Evaluation and comparison of two efficient probabilistic primality testing algorithms*, Theoret. Comput. Sci.**12**(1980), 97--108, MR**82a:68078**.**5**M. O.Rabin,*Probabilistic algorithm for testing primality*, J. Number Theory**12**(1980), 128--138, MR**81f:10003**.

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
with MSC (1991):
11Y11,
11A51

Retrieve articles in all journals with MSC (1991): 11Y11, 11A51

Additional Information

**Ronald Joseph Burthe Jr.**

Email:
ronnie@alpha.math.uga.edu

DOI:
https://doi.org/10.1090/S0025-5718-96-00695-3

Received by editor(s):
May 3, 1994

Article copyright:
© Copyright 1996
American Mathematical Society