×

Explicit primality criteria for \((p-1) p^n-1\). (English) Zbl 1018.11062

Summary: 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.

MSC:

11Y11 Primality
11Y16 Number-theoretic algorithms; complexity
PDFBibTeX XMLCite
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Primes of the form p^k - p^(k-1) - 1, with p prime and k>1.

References:

[1] Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355 – 380. · Zbl 0701.11075
[2] Wieb Bosma, Explicit primality criteria for \?\cdot 2^{\?}\pm 1, Math. Comp. 61 (1993), no. 203, 97 – 109, S7 – S9. · Zbl 0817.11060
[3] D. H. Lehmer. An extended theory of Lucas’ functions. Annals of Mathematics, 31:419-448, 1930. · JFM 56.0874.04
[4] E. Lucas. Nouveaux théoremes d‘arithmétique supérieure. Comptes Rendus Acad. des Sciences, Paris, 83:1286-1288, 1876.
[5] 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.
[6] H. C. Williams, The primality of \?=2\?3\(^{n}\)-1, Canad. Math. Bull. 15 (1972), 585 – 589. · Zbl 0251.10009 · doi:10.4153/CMB-1972-101-7
[7] H. C. Williams, The primality of certain integers of the form 2\?\?\(^{n}\)-1, Acta Arith. 39 (1981), no. 1, 7 – 17. · Zbl 0475.10003
[8] 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. · Zbl 0482.10007
[9] H. C. Williams, Effective primality tests for some integers of the forms \?5\(^{n}\)-1 and \?7\(^{n}\)-1, Math. Comp. 48 (1987), no. 177, 385 – 403. · Zbl 0608.10003
[10] H. C. Williams. Édouard Lucas and Primality Testing, volume 22 of Canadian Mathematical Society Series of Monographs and Advanced Texts. Wiley, NY, 1998. CMP 98:15
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.