A primality test for 𝐾𝑝ⁿ+1 numbers

Grau, José; Oller-Marcén, Antonio; Sadornil, Daniel

doi:10.1090/S0025-5718-2014-02849-4

A primality test for $Kp^n+1$ numbers
HTML articles powered by AMS MathViewer

by José María Grau, Antonio M. Oller-Marcén and Daniel Sadornil PDF

Math. Comp. 84 (2015), 505-512 Request permission

Abstract:

In this paper we generalize the classical Proth’s theorem and the Miller-Rabin test for integers of the form $N=Kp^n+1$. For these families, we present variations on the classical Pocklington’s results and, in particular, a primality test whose computational complexity is $\widetilde {O}(\log ^2 N)$ and, what is more important, that requires only one modular exponentiation modulo $N$ similar to that of Fermat’s test.

References

Pedro Berrizbeitia and T. G. Berry, Cubic reciprocity and generalised Lucas-Lehmer tests for primality of $A\cdot 3^n\pm 1$, Proc. Amer. Math. Soc. 127 (1999), no. 7, 1923–1925. MR 1487359, DOI 10.1090/S0002-9939-99-04786-3
Pedro Berrizbeitia and T. G. Berry, Generalized strong pseudoprime tests and applications, J. Symbolic Comput. 30 (2000), no. 2, 151–160. MR 1777169, DOI 10.1006/jsco.1999.0343
Pedro Berrizbeitia, T. G. Berry, and Juan Tena-Ayuso, A generalization of Proth’s theorem, Acta Arith. 110 (2003), no. 2, 107–115. MR 2008078, DOI 10.4064/aa110-2-1
Pedro Berrizbeitia and Boris Iskra, Deterministic primality test for numbers of the form $A^2\cdot 3^n+1,\ n\ge 3$ odd, Proc. Amer. Math. Soc. 130 (2002), no. 2, 363–365. MR 1862113, DOI 10.1090/S0002-9939-01-06100-7
Pedro Berrizbeitia and Aurora Olivieri, A generalization of Miller’s primality theorem, Proc. Amer. Math. Soc. 136 (2008), no. 9, 3095–3104. MR 2407072, DOI 10.1090/S0002-9939-08-09303-9
Wieb Bosma, Cubic reciprocity and explicit primality tests for $h\cdot 3^k\pm 1$, High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams, Fields Inst. Commun., vol. 41, Amer. Math. Soc., Providence, RI, 2004, pp. 77–89. MR 2076210, DOI 10.1086/382215
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
Richard Crandall and Carl Pomerance, Prime numbers, 2nd ed., Springer, New York, 2005. A computational perspective. MR 2156291
José María Grau and Antonio M. Oller-Marcén, An $\tilde {O}(\log ^{2}(N))$ time primality test for generalized Cullen numbers, Math. Comp. 80 (2011), no. 276, 2315–2323. MR 2813363, DOI 10.1090/S0025-5718-2011-02489-0
Andreas Guthmann, Effective primality tests for integers of the forms $N=k\cdot 3^n+1$ and $N=k\cdot 2^m3^n+1$, BIT 32 (1992), no. 3, 529–534. MR 1179238, DOI 10.1007/BF02074886
Franz Lemmermeyer, Reciprocity laws, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2000. From Euler to Eisenstein. MR 1761696, DOI 10.1007/978-3-662-12893-0
H. W. Lenstra Jr. and P. Stevenhagen, Artin reciprocity and Mersenne primes, Nieuw Arch. Wiskd. (5) 1 (2000), no. 1, 44–54. MR 1760775
Théophile Pépin, Sur la Formule $2^{2^n}+1$, C. R. Acad. Sci. Paris, 85:329–331, 1877.
H. C. Pocklington, The determination of the prime or composite nature of large numbers by fermat’s theorem, Proc. Cambridge Philos. Soc., 18:29–30, 1914.
François Proth. Théorémes sur les nombre premiers, C. R. Acad. Sci. Paris, 87:926, 1878.
A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
H. C. Williams, A note on the primality of $6^{2^n}+1$ and $10^{2^n}+1$, Fibonacci Quart. 26 (1988), no. 4, 296–305. MR 967648
H. C. Williams and C. R. Zarnke, Some prime numbers of the forms $2A3^{n}+1$ and $2A3^{n}-1$, Math. Comp. 26 (1972), 995–998. MR 314747, DOI 10.1090/S0025-5718-1972-0314747-X