An $\tilde {O}(\log ^2(N))$ time primality test for generalized Cullen numbers
HTML articles powered by AMS MathViewer
- by José María Grau and Antonio M. Oller-Marcén PDF
- Math. Comp. 80 (2011), 2315-2323 Request permission
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
- 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, DOI 10.2307/2006975
- Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781–793. MR 2123939, DOI 10.4007/annals.2004.160.781
- Pedro Berrizbeitia, Sharpening “PRIMES is in $P$” for a large family of numbers, Math. Comp. 74 (2005), no. 252, 2043–2059. MR 2164112, DOI 10.1090/S0025-5718-05-01727-8
- 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” (http://campus.usal.es/ tjtn2009/doc/abstracts.pdf).
- H. Cohen and H. W. Lenstra Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), no. 165, 297–330. MR 726006, DOI 10.1090/S0025-5718-1984-0726006-X
- James Cullen, Question 15897, Educ. Times (1905), no. Dec., 534.
- A. Cunningham and H.J. Woodall, Factorisation of ${Q}=(2^q\mp q)$ and $(q2^q\mp 1)$, Messenger Math. 47 (1917), 1–38.
- Harvey Dubner, Generalized Cullen numbers, J. Recreat. Math. 21 (1989), 190–194.
- Richard K. Guy, Unsolved problems in number theory, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR 2076335, DOI 10.1007/978-0-387-26677-0
- C. Hooley, Applications of sieve methods to the theory of numbers, Cambridge Tracts in Mathematics, No. 70, Cambridge University Press, Cambridge-New York-Melbourne, 1976. MR 0404173
- 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, DOI 10.1090/S0025-5718-1995-1308456-3
- 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, DOI 10.1007/978-3-642-60408-9_{1}5
- Michal Křížek, Florian Luca, and Lawrence Somer, 17 lectures on Fermat numbers, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, vol. 9, Springer-Verlag, New York, 2001. From number theory to geometry; With a foreword by Alena Šolcová. MR 1866957, DOI 10.1007/978-0-387-21850-2
- F. Luca, On the greatest common divisor of two Cullen numbers, Abh. Math. Sem. Univ. Hamburg 73 (2003), 253–270. MR 2028519, DOI 10.1007/BF02941281
- Florian Luca and Igor E. Shparlinski, Pseudoprime Cullen and Woodall numbers, Colloq. Math. 107 (2007), no. 1, 35–43. MR 2283130, DOI 10.4064/cm107-1-5
- Édouard Lucas, Sur la recherche des grands nombres premiers, Assoc. Francaise p. l’Avanc. des Science. Comptes Rendus (1876), no. 5, 61–68.
- Francois Proth, Théorèmes sur les nombres premiers, Comptes Rendus Acad. des Sciences, Paris (1878), no. 87, 926.
- Raphael M. Robinson, A report on primes of the form $k\cdot 2^{n}+1$ and on factors of Fermat numbers, Proc. Amer. Math. Soc. 9 (1958), 673–681. MR 96614, DOI 10.1090/S0002-9939-1958-0096614-7
- 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
- Hugh C. Williams, Édouard Lucas and primality testing, Canadian Mathematical Society Series of Monographs and Advanced Texts, vol. 22, John Wiley & Sons, Inc., New York, 1998. A Wiley-Interscience Publication. MR 1632793
Additional Information
- José María Grau
- Affiliation: Department of Mathematics, University of Oviedo, Avda. Calvo Sotelo s/n, 33007, Oviedo, Spain
- Email: grau@uniovi.es
- Antonio M. Oller-Marcén
- Affiliation: University of Zaragoza, Department of Mathematics, C/Pedro Cerbuna 12, 50009 Zaragoza, Spain
- Email: oller@unizar.es
- Received by editor(s): July 8, 2010
- Received by editor(s) in revised form: September 21, 2010
- Published electronically: March 11, 2011
- © Copyright 2011
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 80 (2011), 2315-2323
- MSC (2010): Primary 11Y11, 11Y16, 11A51, 11B99
- DOI: https://doi.org/10.1090/S0025-5718-2011-02489-0
- MathSciNet review: 2813363