Explicit primality criteria for \(h \cdot 2^n \pm 1\) (Q284473)

É. 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 \textit{seed}, see [\textit{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). \textit{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 \textit{P. Berrizbeitia} and \textit{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 \textit{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\).