A Generalized Lucasian Primality Test

Numbers of special forms, such as M_h,n = h·2ⁿ ± 1 (h,n positive integers with h odd), are often interested by mathematicians. The classical Lucas-Lehmer test is a fast polynomial-time primality-proof algorithm for Mersenne primes 2^p - 1. The test involves a Lucas sequence {w_j} which is defined from a given initial value (called seed) w₀ = 4 for all odd prime p, and w_j+1 = w_j² - 2 for j ≥ 0 by recurrence. The Lucas-Lehmer test generalizes to a Lucasian primality test for M_h,n. In the generalized test, the seed w₀ depends on n as well as on h. However, following the analogy with Mersenne numbers, our philosophy is to fix h and search for primes in the family M_h,n with n increasing. Thus it is certainly desirable to have a seed independent of n, if possible. It is a easy task for the case h (?) 0 mod 3. For each odd h ≡ 0 mod 3, h < 10⁵ (but h ≠ 4^m - 1), Bosnia [Explicity primality criteria for h · 2ⁿ ± 1, Math. Comp. 61 (1993), 97-109, s7-s9. MR 1197510 (94c:11005)] designed algorithms for determining a finite set such that, for any n, there is a suitable seed for testing primality of M_h,n. But for h = 4^m - 1, he proved that such a finite set does not exist. Berrizbeitia and Berry [Biquadratic reciprocity and a Lucasian Primality test, Math. Comp. 73 (2004), 1559-1564. MR 2047101 (2004m:11005)] present a test which allows one to test primality of M_h,n = h · 2ⁿ ± 1 by means of a Lucasian sequence with a seed determined only by h, provided h(?)0 mod 5. In particular, when h = 4^m - 1 (m odd), they have a test with a single seed depending only on h.In this paper, we first present a generalized test which allows one to test primality of M_h,n= h · 2ⁿ ± 1 by means of a Lucasian sequence with a seed determined only by h, provided h (?) 0 mod q where q is any prime ≡ 1 mod 4. Our generalized test includes Berrizbeitia-Berry test as a special case and can treat the two cases h · 2ⁿ ± 1 simultaneously as the Berrizbeitia-Berry test does. Then we give pseudocode for our algorithm and some example primes the primality of which is proved by our algorithm. At last, we determine finite sets of seeds for h ≡ 0 mod 15, which are simpler and more practical than Bosnia's sets for the case h ≡ 0 mod 3.