Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

A primality test for $ Kp^n+1$ numbers


Authors: José María Grau, Antonio M. Oller-Marcén and Daniel Sadornil
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
Published electronically: June 10, 2014
MathSciNet review: 3266973
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 (99j:11006), https://doi.org/10.1090/S0002-9939-99-04786-3
  • [2] Pedro Berrizbeitia and T. G. Berry, Generalized strong pseudoprime tests and applications, J. Symbolic Comput. 30 (2000), no. 2, 151-160. MR 1777169 (2001f:11201), https://doi.org/10.1006/jsco.1999.0343
  • [3] 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 (2004g:11003), https://doi.org/10.4064/aa110-2-1
  • [4] 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 (electronic). MR 1862113 (2002i:11007), https://doi.org/10.1090/S0002-9939-01-06100-7
  • [5] Pedro Berrizbeitia and Aurora Olivieri, A generalization of Miller's primality theorem, Proc. Amer. Math. Soc. 136 (2008), no. 9, 3095-3104. MR 2407072 (2009g:11164), https://doi.org/10.1090/S0002-9939-08-09303-9
  • [6] 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 (2005e:11002)
  • [7] 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 0384673 (52 #5546)
  • [8] Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, 2nd ed., Springer, New York, 2005. MR 2156291 (2006a:11005)
  • [9] 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 (2012d:11244), https://doi.org/10.1090/S0025-5718-2011-02489-0
  • [10] 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 (93h:11008), https://doi.org/10.1007/BF02074886
  • [11] Franz Lemmermeyer, Reciprocity Laws: From Euler to Eisenstein, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2000. MR 1761696 (2001i:11009)
  • [12] H. W. Lenstra Jr. and P. Stevenhagen, Artin reciprocity and Mersenne primes, Nieuw Arch. Wiskd. (5) 1 (2000), no. 1, 44-54. MR 1760775 (2001h:11006)
  • [13] Théophile Pépin, Sur la Formule $ 2^{2^n}+1$, C. R. Acad. Sci. Paris, 85:329-331, 1877.
  • [14] 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.
  • [15] François Proth. Théorémes sur les nombre premiers, C. R. Acad. Sci. Paris, 87:926, 1878.
  • [16] A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281-292 (German, with English summary). MR 0292344 (45 #1431)
  • [17] 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 (89i:11013)
  • [18] 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 0314747 (47 #3299)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y11, 11Y16, 11A51, 11B99

Retrieve articles in all journals with MSC (2010): 11Y11, 11Y16, 11A51, 11B99


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

DOI: https://doi.org/10.1090/S0025-5718-2014-02849-4
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.
Article copyright: © Copyright 2014 American Mathematical Society

American Mathematical Society