Some observations on primality testing
HTML articles powered by AMS MathViewer
- by H. C. Williams and R. Holte PDF
- Math. Comp. 32 (1978), 905-917 Request permission
Abstract:
Let N be an integer which is to be tested for primality. Previous methods of ascertaining the primality of N make use of factors of $N \pm 1$, ${N^2} \pm N + 1$, and ${N^2} + 1$ in order to increase the size of any possible prime divisor of N until it is impossible for N to be the product of two or more primes. These methods usually 2 work as long as $N < {K^2}$ , where K is $1/12$ of the product of the known prime power factors of $N \pm 1$, ${N^2} \pm N + 1$, and ${N^2} + 1$. In this paper a technique is described which, when used in conjunction with these methods, will often determine the pri mality of N when $N < l{K^3}$ and l is small.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
- 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
- Noel B. Slater, Gaps and steps for the sequence $n\theta \ \textrm {mod}\ 1$, Proc. Cambridge Philos. Soc. 63 (1967), 1115β1123. MR 217019, DOI 10.1017/s0305004100042195
- R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no.Β 1, 84β85. MR 429721, DOI 10.1137/0206006
- 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
Additional Information
- © Copyright 1978 American Mathematical Society
- Journal: Math. Comp. 32 (1978), 905-917
- MSC: Primary 10A25; Secondary 10-04
- DOI: https://doi.org/10.1090/S0025-5718-1978-0476625-0
- MathSciNet review: 0476625