Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



An $ \tilde{O}(\log^2(N))$ time primality test for generalized Cullen numbers

Authors: José María Grau and Antonio M. Oller-Marcén
Journal: Math. Comp. 80 (2011), 2315-2323
MSC (2010): Primary 11Y11, 11Y16, 11A51, 11B99
Published electronically: March 11, 2011
MathSciNet review: 2813363
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Generalized Cullen Numbers are positive integers of the form $ C_b(n):=nb^n+1$. In this work we generalize some known divisibility properties of Cullen Numbers and present two primality tests for this family of integers. The first test is based in the following property of primes from this family: $ n^{b^{n}}\equiv (-1)^{b}$ (mod $ nb^n+1$). It is stronger and has less computational cost than Fermat's test (to bases $ b$ and $ n$) and than Miller-Rabin's test (if $ b$ is odd, to base $ n$). Pseudoprimes for this new test seem to be very scarce, only 4 pseudoprimes have been found among the many millions of Generalized Cullen Numbers tested. We also present a second, more demanding, test for which no pseudoprimes have been found. These tests lead to an algorithm, running in $ \tilde{O}(\log^2(N))$ time, which might be very useful in the search of Generalized Cullen Primes.

References [Enhancements On Off] (What's this?)

  • 1. Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), no. 1, 173-206. MR 683806 (84e:10008)
  • 2. Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781-793. MR 2123939 (2006a:11170)
  • 3. Pedro Berrizbeitia, Sharpening ``PRIMES is in $ P$'' for a large family of numbers, Math. Comp. 74 (2005), no. 252, 2043-2059 (electronic). MR 2164112 (2006e:11191)
  • 4. Pedro Berrizbeitia and José Gregorio Fernandes, Observaciones sobre la primalidad de los números de cullen, Short communication in ``Terceras Jornadas de Teoría de Números'' ( tjtn2009/doc/abstracts.pdf).
  • 5. H. Cohen and H. W. Lenstra, Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), no. 165, 297-330. MR 726006 (86g:11078)
  • 6. James Cullen, Question 15897, Educ. Times (1905), no. Dec., 534.
  • 7. A. Cunningham and H.J. Woodall, Factorisation of $ {Q}=(2^q\mp q)$ and $ (q2^q\mp 1)$, Messenger Math. 47 (1917), 1-38.
  • 8. Harvey Dubner, Generalized Cullen numbers, J. Recreat. Math. 21 (1989), 190-194.
  • 9. Richard K. Guy, Unsolved problems in number theory, third ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR 2076335 (2005h:11003)
  • 10. C. Hooley, Applications of sieve methods to the theory of numbers, Cambridge University Press, Cambridge, 1976, Cambridge Tracts in Mathematics, No. 70. MR 0404173 (53:7976)
  • 11. Wilfrid Keller, New Cullen primes, Math. Comp. 64 (1995), no. 212, 1733-1741, S39-S46, With a biographical sketch of James Cullen by T. G. Holt and a supplement by Keller and Wolfgang Niebuhr. MR 1308456 (95m:11015)
  • 12. Sergei Konyagin and Carl Pomerance, On primes recognizable in deterministic polynomial time, The mathematics of Paul Erdős, I, Algorithms Combin., vol. 13, Springer, Berlin, 1997, pp. 176-198. MR 1425185 (98a:11184)
  • 13. Michal Křížek, Florian Luca, and Lawrence Somer, 17 lectures on Fermat numbers, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 9, Springer-Verlag, New York, 2001, From number theory to geometry, With a foreword by Alena Šolcová. MR 1866957 (2002i:11001)
  • 14. F. Luca, On the greatest common divisor of two Cullen numbers, Abh. Math. Sem. Univ. Hamburg 73 (2003), 253-270. MR 2028519 (2004i:11001)
  • 15. Florian Luca and Igor E. Shparlinski, Pseudoprime Cullen and Woodall numbers, Colloq. Math. 107 (2007), no. 1, 35-43. MR 2283130 (2007i:11127)
  • 16. Édouard Lucas, Sur la recherche des grands nombres premiers, Assoc. Francaise p. l'Avanc. des Science. Comptes Rendus (1876), no. 5, 61-68.
  • 17. Francois Proth, Théorèmes sur les nombres premiers, Comptes Rendus Acad. des Sciences, Paris (1878), no. 87, 926.
  • 18. Raphael M. Robinson, A report on primes of the form $ k\cdot 2\sp{n}+1$ and on factors of Fermat numbers, Proc. Amer. Math. Soc. 9 (1958), 673-681. MR 0096614 (20:3097)
  • 19. A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281-292. MR 0292344 (45:1431)
  • 20. Hugh C. Williams, Édouard Lucas and primality testing, Canadian Mathematical Society Series of Monographs and Advanced Texts, 22, John Wiley & Sons Inc., New York, 1998, A Wiley-Interscience Publication. MR 1632793 (2000b:11139)

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: Department of Mathematics, University of Oviedo, Avda. Calvo Sotelo s/n, 33007, Oviedo, Spain

Antonio M. Oller-Marcén
Affiliation: University of Zaragoza, Department of Mathematics, C/Pedro Cerbuna 12, 50009 Zaragoza, Spain

Received by editor(s): July 8, 2010
Received by editor(s) in revised form: September 21, 2010
Published electronically: March 11, 2011
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society