A primality test for \(4Kp^n-1\) numbers (Q2287882)

Classical Lucasian type primality tests provide primality criteria for an integer \(N\) written in a specific form and based on the use of a recursive sequence. The initial value, \(S_0\), of the recursion usually depends on the specific parameter values used to represent \(N\). Motivated by this dependence of \(S_0\) on the specific \(N\), the authors provide an alternative in which the necessity is dropped in order to obtain a laxer sufficient primality condition independent of any parameters of \(N\) in a given parametrised set of integers. The authors present in Corollary 1 a Lucasian type primality test for numbers written in the form \(N=4 K p^n - 1\), in which \(p\) is an odd prime, \(n\geq 1\) and \(K\) an odd integer with \(4K \leq p^n\). Moreover, in Corollary 2 and setting \(p=2\), a Gaussian analogue to the classical Lucas-Lehmer-Riesel test is presented. In Section 4 the computational complexity of their proposed algorithm is discussed. Finally, in Section 5 the algorithm is compared to other methods and the probability with which a prime is correctly certified by the algorithm is discussed as well. It is noted that similar results have been obtained by different authors [E. L. Roettger et al., Des. Codes Cryptography 77, No. 2-3, 515--539 (2015; Zbl 1364.11161)], but that the presentation of the results is novel and original.