Abstract:
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)$.