Explicit primality criteria for $(p-1)p^n-1$
HTML articles powered by AMS MathViewer
- by Andreas Stein and H. C. Williams PDF
- Math. Comp. 69 (2000), 1721-1734 Request permission
Abstract:
Deterministic polynomial time primality criteria for $2^n-1$ have been known since the work of Lucas in 1876–1878. Little is known, however, about the existence of deterministic polynomial time primality tests for numbers of the more general form $N_n=(p-1) p^n-1$, where $p$ is any fixed prime. When $n>(p-1)/2$ we show that it is always possible to produce a Lucas-like deterministic test for the primality of $N_n$ which requires that only $O(q (p+\log q)+p^3+\log N_n)$ modular multiplications be performed modulo $N_n$, as long as we can find a prime $q$ of the form $1+k p$ such that $N_n^{ k}-1$ is not divisible by $q$. We also show that for all $p$ with $3<p<10^7$ such a $q$ can be found very readily, and that the most difficult case in which to find a $q$ appears, somewhat surprisingly, to be that for $p=3$. Some explanation is provided as to why this case is so difficult.References
- Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355–380. MR 1023756, DOI 10.1090/S0025-5718-1990-1023756-8
- Wieb Bosma, Explicit primality criteria for $h\cdot 2^k\pm 1$, Math. Comp. 61 (1993), no. 203, 97–109, S7–S9. MR 1197510, DOI 10.1090/S0025-5718-1993-1197510-3
- D. H. Lehmer. An extended theory of Lucas’ functions. Annals of Mathematics, 31:419–448, 1930.
- E. Lucas. Nouveaux théoremes d‘arithmétique supérieure. Comptes Rendus Acad. des Sciences, Paris, 83:1286–1288, 1876.
- H. C. Williams, An algorithm for determining certain large primes, Proceedings Second Louisiana Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1971) Louisiana State Univ., Baton Rouge, La., 1971, pp. 533–556. MR 0319874
- H. C. Williams, The primality of $N=2A3^{n}-1$, Canad. Math. Bull. 15 (1972), 585–589. MR 311559, DOI 10.4153/CMB-1972-101-7
- H. C. Williams, The primality of certain integers of the form $2Ar^{n}-1$, Acta Arith. 39 (1981), no. 1, 7–17. MR 638738, DOI 10.4064/aa-39-1-7-17
- H. C. Williams, A class of primality tests for trinomials which includes the Lucas-Lehmer test, Pacific J. Math. 98 (1982), no. 2, 477–494. MR 650024
- H. C. Williams, Effective primality tests for some integers of the forms $A5^n-1$ and $A7^n-1$, Math. Comp. 48 (1987), no. 177, 385–403. MR 866123, DOI 10.1090/S0025-5718-1987-0866123-X
- H. C. Williams. Édouard Lucas and Primality Testing, volume 22 of Canadian Mathematical Society Series of Monographs and Advanced Texts. Wiley, NY, 1998.
Additional Information
- Andreas Stein
- Affiliation: University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario, Canada N2L 3G1
- Email: astein@cacr.math.uwaterloo.ca
- H. C. Williams
- Affiliation: University of Manitoba, Department of Computer Science, Winnipeg, Manitoba, Canada R3T 2N2
- Email: williams@cs.umanitoba.ca
- Received by editor(s): October 24, 1997
- Received by editor(s) in revised form: October 23, 1998
- Published electronically: February 23, 2000
- Additional Notes: Research supported by NSERC of Canada Grant $\#A7649$.
- © Copyright 2000 American Mathematical Society
- Journal: Math. Comp. 69 (2000), 1721-1734
- MSC (1991): Primary 11Y11; Secondary 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-00-01212-6
- MathSciNet review: 1697651