RetroSearch Browse

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://doi.org/10.1090/S0025-5718-1982-0658231-9 below:

Website Navigation

AMS :: Mathematics of Computation

Journals Home eContent Search About Mathematics of Computation Editorial Board Author and Submission Information Journal Policies Subscription Information Journal Email Notifications Remote Access Strong primality tests that are not sufficient
HTML articles powered by AMS MathViewer

by William Adams and Daniel Shanks PDF

Math. Comp. 39 (1982), 255-300 Request permission

Abstract: A detailed investigation is given of the possible use of cubic recurrences in primality tests. No attempt is made in this abstract to cover all of the many topics examined in the paper. Define a doubly infinite set of sequences $A(n)$ by \[ A(n + 3) = rA(n + 2) - sA(n + 1) + A(n)\] with $A( - 1) = s$, $A(0) = 3$, and $A(1) = r$. If n is prime, $A(n) \equiv A(1)\;\pmod n$. Perrin asked if any composite satisfies this congruence if $r = 0$, $s = - 1$. The answer is yes, and our first example leads us to strengthen the condition by introducing the "signature" of n: \[ A( - n - 1),A( - n),A( - n + 1),A(n - 1),A(n),A(n + 1)\] $\bmod n$. Primes have three types of signatures depending on how they split in the cubic field generated by ${x^3} - r{x^2} + sx - 1 = 0$. Composites with "acceptable" signatures do exist but are very rare. The S-type signature, which corresponds to the completely split primes, has a very special role, and it may even be that I and Q type composites do not occur in Perrinâs sequence even though the I and Q primes comprise $5/6$ths of all primes. $A(n)\;\pmod n$ is easily computable in $O(\log n)$ operations. The paper closes with a p-adic analysis. This powerful tool sets the stage for our [12] which will be Part II of the paper. References

LâIntermÃ©diare des Math.

ibid.

Recurring Sequences

Daniel Shanks, Calculation and applications of Epstein zeta functions, Math. Comp. 29 (1975), 271â287. MR 409357, DOI 10.1090/S0025-5718-1975-0409357-2
Daniel Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Congressus Numerantium, No. VII, Utilitas Math., Winnipeg, Man., 1973, pp.Â 51â70. MR 0371855

Seminumerical Algorithms

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

ibid.

Daniel Shanks, A survey of quadratic, cubic and quartic algebraic number fields (from a computational point of view), Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Congressus Numerantium, No. XVII, Utilitas Math., Winnipeg, Man., 1976, pp.Â 15â40. MR 0453691
Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp.Â 415â440. MR 0316385
Daniel Shanks, Solved and unsolved problems in number theory, 2nd ed., Chelsea Publishing Co., New York, 1978. MR 516658
William G. Spohn Jr., Letter to the editor: âIncredible identitiesâ (Fibonacci Quart. 12 (1974), 271, 280) by Daniel Shanks, Fibonacci Quart. 14 (1976), no.Â 1, 12. MR 384744