Pseudoprimes for higher-order linear recurrence sequences
HTML articles powered by AMS MathViewer
- by S. Gurak PDF
- Math. Comp. 55 (1990), 783-813 Request permission
Abstract:
With the advent of high-speed computing, there is a rekindled interest in the problem of determining when a given whole number $N > 1$ is prime or composite. While complex algorithms have been developed to settle this for 200-digit numbers in a matter of minutes with a supercomputer, there is a need for simpler, more practical algorithms for dealing with numbers of a more modest size. Such practical tests for primality have recently been given (running in deterministic linear time) in terms of pseudoprimes for certain second- or third-order linear recurrence sequences. Here, a powerful general theory is described to characterize pseudoprimes for higher-order recurrence sequences. This characterization leads to a broadening and strengthening of practical primality tests based on such pseudoprimes.References
- William Adams and Daniel Shanks, Strong primality tests that are not sufficient, Math. Comp. 39 (1982), no. 159, 255–300. MR 658231, DOI 10.1090/S0025-5718-1982-0658231-9
- William W. Adams, Characterizing pseudoprimes for third-order linear recurrences, Math. Comp. 48 (1987), no. 177, 1–15. MR 866094, DOI 10.1090/S0025-5718-1987-0866094-6 E. Artin, Galois theory, 2nd ed., University of Notre Dame, 1946.
- E. Artin and J. Tate, Class field theory, W. A. Benjamin, Inc., New York-Amsterdam, 1968. MR 0223335
- 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
- R. D. Carmichael, On Composite Numbers $P$ Which Satisfy the Fermat Congruence $a^{P-1} \equiv 1 \operatorname {mod} P$, Amer. Math. Monthly 19 (1912), no. 2, 22–27. MR 1517641, DOI 10.2307/2972687 L. E. Dickson, Elementary theory of equations, Wiley, New York.
- H. J. A. Duparc, Periodicity properties of recurring sequences. II, Nederl. Akad. Wetensch. Proc. Ser. A. 57 = Indag. Math. 16 (1954), 473–485. MR 0067135
- S. Gurak, Cubic and biquadratic pseudoprimes of Lucas type, Théorie des nombres (Quebec, PQ, 1987) de Gruyter, Berlin, 1989, pp. 330–347. MR 1024573
- S. Gurak, On the representation theory for full decomposable forms, J. Number Theory 13 (1981), no. 4, 421–442. MR 642918, DOI 10.1016/0022-314X(81)90034-2
- 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. MR 829639, DOI 10.1090/S0025-5718-1986-0829639-7
- Edouard Lucas, Theorie des Fonctions Numeriques Simplement Periodiques, Amer. J. Math. 1 (1878), no. 4, 289–321 (French). MR 1505176, DOI 10.2307/2369373
- Carl Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), no. 156, 587–593. MR 628717, DOI 10.1090/S0025-5718-1981-0628717-0
- Carl Pomerance, A new lower bound for the pseudoprime counting function, Illinois J. Math. 26 (1982), no. 1, 4–9. MR 638549
- 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 B. L. van der Waerden, Modern algebra, vols. 1, 2, Ungar, New York, 1949-1950.
- Morgan Ward, Arithmetical properties of sequences in rings, Ann. of Math. (2) 39 (1938), no. 1, 210–219. MR 1503399, DOI 10.2307/1968724
Additional Information
- © Copyright 1990 American Mathematical Society
- Journal: Math. Comp. 55 (1990), 783-813
- MSC: Primary 11Y11; Secondary 11A51, 11B37, 11B50
- DOI: https://doi.org/10.1090/S0025-5718-1990-1035934-2
- MathSciNet review: 1035934