Primality testing for numbers of the form \(h\cdot 2^n\pm 1\) (Q2330377)

In this paper a primality test for numbers of the form \(M= h 2^n \pm 1\), where \(n > 1\) is a positive integer and \(h < 2^n\) is odd, is presented. Let \(p \equiv 1\ (\bmod\ 4)\) be a prime satisfying \((M/p) = -1\) (where \((\cdot/p)\) is the Legendre symbol) and \(\alpha\in Z[\sqrt{-1}]\) such that \(p = \alpha \bar{\alpha}\). Let \(s_k = s_{k-1}^2-2\) be the Lucas sequence with seed \(s_0 = (\alpha/\bar{\alpha})^h + (\alpha/\bar{\alpha})^h\). Then \(M\) is prime if and only if \(s_{n-2}\equiv 0\ (\bmod\ M)\). This result provides us with a primality test for the above numbers which runs in \(\tilde{O}(\log^2M)\) bit operations.