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
DOI: https://doi.org/10.1090/S0025-5718-2011-02489-0
Published electronically: March 11, 2011
MathSciNet review: 2813363
Full-text PDF Free Access

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?)


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
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

DOI: https://doi.org/10.1090/S0025-5718-2011-02489-0
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.