×

zbMATH — the first resource for mathematics

Frobenius pseudoprimes. (English) Zbl 1011.11079
Summary: The proliferation of probable prime tests in recent years has produced a plethora of definitions with the word “pseudoprime” in them. Examples include pseudoprimes, Euler pseudoprimes, strong pseudoprimes, Lucas pseudoprimes, strong Lucas pseudoprimes, extra strong Lucas pseudoprimes and Perrin pseudoprimes. Though these tests represent a wealth of ideas, they exist as a hodge-podge of definitions rather than as examples of a more general theory. It is the goal of this paper to present a way of viewing many of these tests as special cases of a general principle, as well as to reformulate them in the context of finite fields.
One aim of the reformulation is to enable the creation of stronger tests; another is to aid in proving results about large classes of pseudoprimes.

MSC:
11Y11 Primality
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] William W. Adams, Characterizing pseudoprimes for third-order linear recurrences, Math. Comp. 48 (1987), no. 177, 1 – 15. · Zbl 0614.10005
[2] William Adams and Daniel Shanks, Strong primality tests that are not sufficient, Math. Comp. 39 (1982), no. 159, 255 – 300. · Zbl 0492.10005
[3] W. R. Alford, Andrew Granville, and Carl Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703 – 722. · Zbl 0816.11005
[4] W. R. Alford, Andrew Granville, and Carl Pomerance, On the difficulty of finding reliable witnesses, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 1 – 16. · Zbl 0828.11074
[5] Steven Arno, A note on Perrin pseudoprimes, Math. Comp. 56 (1991), no. 193, 371 – 376. · Zbl 0713.11005
[6] A. O. L. Atkin, Intelligent primality test offer, Computational perspectives on number theory (Chicago, IL, 1995) AMS/IP Stud. Adv. Math., vol. 7, Amer. Math. Soc., Providence, RI, 1998, pp. 1 – 11. · Zbl 0928.11054
[7] Robert Baillie and Samuel S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391 – 1417. · Zbl 0458.10003
[8] Daniel M. Gordon, Pseudoprimes on elliptic curves, Théorie des nombres (Quebec, PQ, 1987) de Gruyter, Berlin, 1989, pp. 290 – 305.
[9] Daniel M. Gordon and Carl Pomerance, The distribution of Lucas and elliptic pseudoprimes, Math. Comp. 57 (1991), no. 196, 825 – 838. , https://doi.org/10.1090/S0025-5718-1991-1094951-8 D. M. Gordon and C. Pomerance, Corrigendum: ”The distribution of Lucas and elliptic pseudoprimes” [Math. Comp. 57 (1991), no. 196, 825 – 838; MR1094951 (92h:11081)], Math. Comp. 60 (1993), no. 202, 877. · Zbl 0744.11066
[10] J. Grantham, Frobenius Pseudoprimes, dissertation, University of Georgia, 1997. · Zbl 1011.11079
[11] J. Grantham, A Probable Prime Test With High Confidence, J. Number Theory 72 (1998), 32-47. CMP 98:17 · Zbl 0930.11087
[12] J. Grantham, There Are Infinitely Many Perrin Pseudoprimes. · Zbl 1216.11110
[13] S. Gurak, Pseudoprimes for higher-order linear recurrence sequences, Math. Comp. 55 (1990), no. 192, 783 – 813. · Zbl 0713.11087
[14] Richard K. Guy, Unsolved problems in number theory, 2nd ed., Problem Books in Mathematics, Springer-Verlag, New York, 1994. Unsolved Problems in Intuitive Mathematics, I. · Zbl 0805.11001
[15] Nathan Jacobson, Basic algebra. I, 2nd ed., W. H. Freeman and Company, New York, 1985. · Zbl 0557.16001
[16] G. C. Kurtz, Daniel Shanks, and H. C. Williams, Fast primality tests for numbers less than 50\cdot 10\(^{9}\), Math. Comp. 46 (1986), no. 174, 691 – 701. · Zbl 0594.10001
[17] H. W. Lenstra Jr., Primality testing, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 55 – 77. · Zbl 0507.10003
[18] Z. Mo and J. P. Jones, A new primality test using Lucas sequences, preprint.
[19] Louis Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12 (1980), no. 1, 97 – 108. · Zbl 0443.10002
[20] C. Pomerance, Are there counter-examples to the Baillie - PSW primality test?, Dopo Le Parole aangeboden aan Dr. A. K. Lenstra , Amsterdam, 1984.
[21] Carl Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), no. 156, 587 – 593. · Zbl 0511.10002
[22] 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. · Zbl 0444.10007
[23] Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128 – 138. · Zbl 0426.10006
[24] Raphael M. Robinson, The converse of Fermat’s theorem, Amer. Math. Monthly 64 (1957), 703 – 710. · Zbl 0079.06303
[25] A. Rotkiewicz, On the pseudoprimes of the form \?\?+\? with respect to the sequence of Lehmer, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 20 (1972), 349 – 354 (English, with Russian summary). · Zbl 0249.10012
[26] A. Rotkiewicz, On Euler Lehmer pseudoprimes and strong Lehmer pseudoprimes with parameters \?, \? in arithmetic progressions, Math. Comp. 39 (1982), no. 159, 239 – 247. · Zbl 0492.10002
[27] G. Szekeres, Higher order pseudoprimes in primality testing, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993) Bolyai Soc. Math. Stud., vol. 2, János Bolyai Math. Soc., Budapest, 1996, pp. 451 – 458. · Zbl 0855.11065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.