AN (O)over-tildeO(log(2)(N)) TIME PRIMALITY TEST FOR GENERALIZED CULLEN NUMBERS

作者：Maria Grau Jose; Oller Marcen Antonio M

来源：Mathematics of Computation, 2011, 80(276): 2315-2323.

DOI：10.1090/S0025-5718-2011-02489-0

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: nbn. n(bn) equivalent to (-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 (O) over tilde (log(2)(N)) time, which might be very useful in the search of Generalized Cullen Primes.

• 出版日期2011-10