Проверка на простоту некоторых чисел вида $N=2kp^m-1$

Предлагается алгоритм проверки на простоту чисел вида $N=2kp^m-1$, где $2k<p^m$, $k$ – нечетное натуральное число, $2k<p^m$, $p$ – простое число и $p=3\pmod 4$. Для построения алгоритма используются функции Люка. Вначале приводится алгоритм для проверки чисел вида $N=2k3^m-1$. Затем та же техника применяется для более общих случаев $N=2kp^m-1$. Все приведенные в этой статье алгоритмы имеют сложность $O((\log N)^2 \log\log N \log\log\log N)$.