Lucas pseudoprimes

Authors:
Robert Baillie and Samuel S. Wagstaff

Journal:
Math. Comp. **35** (1980), 1391-1417

MSC:
Primary 10A25

DOI:
https://doi.org/10.1090/S0025-5718-1980-0583518-6

MathSciNet review:
583518

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We define several types of pseudoprimes with respect to Lucas sequences and prove the analogs of various theorems about ordinary pseudoprimes. For example, we show that Lucas pseudoprimes are rare and we count the Lucas sequences modulo *n* with respect to which *n* is a Lucas pseudoprime. We suggest some powerful new primality tests which combine Lucas pseudoprimes with ordinary pseudoprimes. Since these tests require the evaluation of the least number $f(n)$ for which the Jacobi symbol $(f(n)/n)$ is less than 1, we evaluate the average order of the function *f*.

- John Brillhart, D. H. Lehmer, and J. L. Selfridge,
*New primality criteria and factorizations of $2^{m}\pm 1$*, Math. Comp.**29**(1975), 620–647. MR**384673**, DOI https://doi.org/10.1090/S0025-5718-1975-0384673-1
N. G. DE BRUIJN, "On the number of positive integers $\leqslant x$ and free of prime factors $> y$," - D. A. Burgess,
*On character sums and $L$-series*, Proc. London Math. Soc. (3)**12**(1962), 193–206. MR**132733**, DOI https://doi.org/10.1112/plms/s3-12.1.193 - P. D. T. A. Elliott,
*A conjecture of Erdős concerning character sums*, Nederl. Akad. Wetensch. Proc. Ser. A 72=Indag. Math.**31**(1969), 164–171. MR**0242780** - P. D. T. A. Elliott,
*On the mean value of $f(p)$*, Proc. London Math. Soc. (3)**21**(1970), 28–96. MR**266881**, DOI https://doi.org/10.1112/plms/s3-21.1.28 - P. Erdös and M. Kac,
*The Gaussian law of errors in the theory of additive number theoretic functions*, Amer. J. Math.**62**(1940), 738–742. MR**2374**, DOI https://doi.org/10.2307/2371483 - P. Erdös,
*On pseudoprimes and Carmichael numbers*, Publ. Math. Debrecen**4**(1956), 201–206. MR**79031** - Pál Erdős,
*Remarks on number theory. I*, Mat. Lapok**12**(1961), 10–17 (Hungarian, with English and Russian summaries). MR**144869**
G. H. HARDY & E. M. WRIGHT, - D. H. Lehmer,
*An extended theory of Lucas’ functions*, Ann. of Math. (2)**31**(1930), no. 3, 419–448. MR**1502953**, DOI https://doi.org/10.2307/1968235
EMMA LEHMER, "On the infinitude of Fibonacci pseudo-primes," - Edouard Lucas,
*Theorie des Fonctions Numeriques Simplement Periodiques*, Amer. J. Math.**1**(1878), no. 4, 289–321 (French). MR**1505176**, DOI https://doi.org/10.2307/2369373
D. E. G. MALM, "On Monte-Carlo primality tests," - Gary L. Miller,
*Riemann’s hypothesis and tests for primality*, J. Comput. System Sci.**13**(1976), no. 3, 300–317. MR**480295**, DOI https://doi.org/10.1016/S0022-0000%2876%2980043-8 - Ivan Niven and Herbert S. Zuckerman,
*An introduction to the theory of numbers*, 3rd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1972. MR**0344181** - Edward A. Parberry,
*On primes and pseudo-primes related to the Fibonacci sequence*, Fibonacci Quart.**8**(1970), no. 1, 49–60. MR**262199** - 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 https://doi.org/10.1090/S0025-5718-1980-0572872-7 - A. Rotkiewicz,
*On the pseudoprimes with respect to the Lucas sequences*, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys.**21**(1973), 793–797 (English, with Russian summary). MR**332640** - K. Szymiczek,
*On pseudoprimes which are products of distinct primes*, Amer. Math. Monthly**74**(1967), no. 1, 35–37. MR**205921**, DOI https://doi.org/10.2307/2314051 - H. C. Williams and J. S. Judd,
*Determination of the primality of $N$ by using factors of $N^{2}\pm 1$*, Math. Comp.**30**(1976), no. 133, 157–172. MR**396390**, DOI https://doi.org/10.1090/S0025-5718-1976-0396390-3 - H. C. Williams and J. S. Judd,
*Some algorithms for prime testing using generalized Lehmer functions*, Math. Comp.**30**(1976), no. 136, 867–886. MR**414473**, DOI https://doi.org/10.1090/S0025-5718-1976-0414473-6 - H. C. Williams,
*On numbers analogous to the Carmichael numbers*, Canad. Math. Bull.**20**(1977), no. 1, 133–143. MR**447099**, DOI https://doi.org/10.4153/CMB-1977-025-9 - H. C. Williams and R. Holte,
*Some observations on primality testing*, Math. Comp.**32**(1978), no. 143, 905–917. MR**476625**, DOI https://doi.org/10.1090/S0025-5718-1978-0476625-0 - Masataka Yorinaga,
*A technique of numerical production of a sequence of pseudo-prime numbers*, Math. J. Okayama Univ.**19**(1976/77), no. 1, 1–4. MR**432522** - Masataka Yorinaga,
*On a congruencial property of Fibonacci numbers–numerical experiments*, Math. J. Okayama Univ.**19**(1976/77), no. 1, 5–10. MR**432525** - Masataka Yorinaga,
*On a congruencial property of Fibonacci numbers–considerations and remarks*, Math. J. Okayama Univ.**19**(1976/77), no. 1, 11–17. MR**432526** - A. Rotkiewicz,
*On Lucas numbers with two intrinsic prime divisors*, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys.**10**(1962), 229–232. MR**139592**

*Indag. Math.*, v. 13, 1951, pp. 50-60. MR

**13**, 724.

*An Introduction to the Theory of Numbers*, 4th ed., Oxford Univ. Press, London, 1959.

*Fibonacci Quart.*, v. 2, 1964, pp. 229-230.

*Notices Amer. Math. Soc.*, v. 24, 1977, p. A-529. Abstract #77T-A22.

Retrieve articles in *Mathematics of Computation*
with MSC:
10A25

Retrieve articles in all journals with MSC: 10A25

Additional Information

Keywords:
Pseudoprime,
Lucas sequence,
Lucas pseudoprime,
strong pseudoprime,
Euler pseudoprime,
primality testing

Article copyright:
© Copyright 1980
American Mathematical Society