Testing numbers of the form $N=2kp^m-1$ for primality

We suggest an algorithm to test numbers of the form $N=2kp^m-1$ for primality, where $2k<p^m$, $k$ is an odd positive integer, $2k<p^m$, $p$ is a prime number, and $p=3\pmod 4$. The algorithm makes use of the Lucas functions. First we present an algorithm to test numbers of the form $N=2k3^m-1$. Then the same technique is used in the more general case where $N=2kp^m-1$. The algorithms suggested here are of complexity $O((\log N)^2 \log\log N \log\log\log N)$.