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
Additional Information
- José María Grau
- Affiliation: Departamento de Matemáticas, Universidad de Oviedo, Avda. Calvo Sotelo, s/n, 33007 Oviedo, Spain
- Email: grau@uniovi.es
- Antonio M. Oller-Marcén
- Affiliation: Centro Universitario de la Defensa de Zaragoza, Ctra. de Huesca, s/n, 50090 Zaragoza, Spain
- Email: oller@unizar.es
- Daniel Sadornil
- Affiliation: Departamento de Matemáticas, Estadística y Computación, Universidad de Cantabria, F. Ciencias, Avda de los Castros s/n, 39005 Santander, Spain
- Email: sadornild@unican.es
- Received by editor(s): June 12, 2012
- Received by editor(s) in revised form: May 13, 2013
- Published electronically: June 10, 2014
- Additional Notes: Daniel Sadornil was partially supported by the Spanish Government under projects MTM2010-21580-C02-02 and MTM2010-16051.
- © Copyright 2014 American Mathematical Society
- Journal: Math. Comp. 84 (2015), 505-512
- MSC (2010): Primary 11Y11, 11Y16, 11A51, 11B99
- DOI: https://doi.org/10.1090/S0025-5718-2014-02849-4
- MathSciNet review: 3266973