É. Lucas, in the XIX century, proposed efficient deterministic primality tests for the two families of numbers \(h2^n+1\) and \(h2^n-1\). These Lucasian tests are given in term of recurrence sequences of integer numbers \(\{u_n\}\), which depends on a recurrence equation and an initial value, the seed, see [H. C. Williams, Édouard Lucas and primality testing. New York, NY: John Wiley & Sons (1998; Zbl 1155.11363)].
The Lucas-Lehmer test, for the Mersenne numbers \(M_p=2^p-1\), takes as seed \(u_0=4\) (a constant). W. Bosma [Math. Comp. 61, No. 203, 97–109 (1993; Zbl 0817.11060)] gave two tests for those two families when \(h\not \equiv 0 \bmod 3\), using in both cases a seed depending only on \(h\) and not on \(n\) and P. Berrizbeitia and T. G. Berry [Math. Comput. 73, No. 247, 1559–1564 (2004; Zbl 1090.11004)] provide a test common to the two families which, assuming \(h\not \equiv 0 \bmod 5\), uses a seed depending only on \(h\).
The aim of the present paper is to give a similar result when \(h\not \equiv 0 \bmod 17\). The paper introduces the notion of a generalized Lucasian sequence \(\{(T_k^1, \dots ,T_k^f)\}\), defined from a given initial value (the seed) \(\{(T_0^1, \ldots,T_0^f)\}\). The primality test (Theorem 3.1, stated in Section 3 and proved in Section 4) treated the two cases \(h2^n\pm 1\) simultaneously and need two generalized Lucasian sequences and, for \(h\not \equiv 0 \bmod 17\) fixed, two seeds (independents of \(n\)). The paper argues that “our generalized Lucasian primality test improves the results of Berrizbeitia and Berry and Bosma”, since for instance when \(h=15\) those tests need infinitely many seeds.
Section 5 studies the computational complexity of the primality test of Theorem 3.1 , proving that for \(M=h2^n\pm 1\) this complexity is \(\tilde O(log^2M)\) bit operations. The paper concludes with an open problem concerning the possibility, for arbitrary \(h\) of a generalized Lucasian primality test for the families \(h2^n\pm 1\) with finitely many seeds depending only on \(h\).