Pseudoprimes for higher-order linear recurrence sequences

Gurak, S.

doi:10.1090/S0025-5718-1990-1035934-2

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

Galois theory

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

Elementary theory of equations

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

Modern algebra

Morgan Ward, Arithmetical properties of sequences in rings, Ann. of Math. (2) 39 (1938), no. 1, 210–219. MR 1503399, DOI 10.2307/1968724