AN O(log~2(N)) TIME PRIMALITY TESTFOR GENERALIZED CULLEN NUMBERS

摘要

Generalized Cullen Numbers are positive integers of the form Cb(n) := nb' + 1. In this work we generalize some known divisibility prop-erties 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=(-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(log~2(N)) time, which might be very useful in the search of Generalized Cullen Primes.