Lucas pseudoprimes

Baillie, Robert; Wagstaff, Samuel S.

doi:10.1090/S0025-5718-1980-0583518-6

Lucas pseudoprimes
HTML articles powered by AMS MathViewer

by Robert Baillie and Samuel S. Wagstaff PDF

Math. Comp. 35 (1980), 1391-1417 Request permission

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.

References

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 10.1090/S0025-5718-1975-0384673-1

Indag. Math.

13

D. A. Burgess, On character sums and $L$-series, Proc. London Math. Soc. (3) 12 (1962), 193–206. MR 132733, DOI 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 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 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

An Introduction to the Theory of Numbers

D. H. Lehmer, An extended theory of Lucas’ functions, Ann. of Math. (2) 31 (1930), no. 3, 419–448. MR 1502953, DOI 10.2307/1968235

Fibonacci Quart.

Edouard Lucas, Theorie des Fonctions Numeriques Simplement Periodiques, Amer. J. Math. 1 (1878), no. 4, 289–321 (French). MR 1505176, DOI 10.2307/2369373

Notices Amer. Math. Soc.

Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, DOI 10.1016/S0022-0000(76)80043-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 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 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 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 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 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 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