The Rabin-Monier theorem for Lucas pseudoprimes
HTML articles powered by AMS MathViewer
- by F. Arnault PDF
- Math. Comp. 66 (1997), 869-881 Request permission
Abstract:
We give bounds on the number of pairs $(P,Q)$ with $0\le P,Q<n$ such that a composite number $n$ is a strong Lucas pseudoprime with respect to the parameters $(P,Q)$.References
- F. Arnault, Rabin-Miller primality test: composite numbers which pass it, Math. Comp. 64 (1995), no. 209, 355–361. MR 1260124, DOI 10.1090/S0025-5718-1995-1260124-2
- —, Constructing Carmichael numbers which are strong pseudoprimes to several bases, J. Symbolic Comput. 20 (1995), 151–161.
- F. Arnault and G. Robin, Sur une fonction associée aux entiers quadratiques, Preprint.
- Robert Baillie and Samuel S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391–1417. MR 583518, DOI 10.1090/S0025-5718-1980-0583518-6
- Gerhard Jaeschke, On strong pseudoprimes to several bases, Math. Comp. 61 (1993), no. 204, 915–926. MR 1192971, DOI 10.1090/S0025-5718-1993-1192971-8
- Z. Mo and J. P. Jones, A new probabilistic primality test using Lucas sequences, Preprint.
- 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
- Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr., The pseudoprimes to $25\cdot 10^{9}$, Math. Comp. 35 (1980), no. 151, 1003–1026. MR 572872, DOI 10.1090/S0025-5718-1980-0572872-7
- 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
- H. C. Williams, On numbers analogous to the Carmichael numbers, Canad. Math. Bull. 20 (1977), no. 1, 133–143. MR 447099, DOI 10.4153/CMB-1977-025-9
Additional Information
- F. Arnault
- Affiliation: Université de Limoges, Faculté des Sciences, URA 1586, Laboratoire d’Arithmétique de Calcul formel et d’Optimisation, 123, av Albert Thomas, 87060 Limoges Cedex, France
- Email: arnault@unilim.fr
- Received by editor(s): August 30, 1994
- Received by editor(s) in revised form: February 28, 1995, and November 6, 1995
- © Copyright 1997 American Mathematical Society
- Journal: Math. Comp. 66 (1997), 869-881
- MSC (1991): Primary 11Y11; Secondary 11A51, 11R11
- DOI: https://doi.org/10.1090/S0025-5718-97-00836-3
- MathSciNet review: 1408370