Geodesic
Testing numbers of the form $N=2kp^m-1$ for primality
Diskretnaya Matematika, Tome 18 (2006) no. 1, pp. 146-155 
E. V. Sadovnik. Testing numbers of the form $N=2kp^m-1$ for primality. Diskretnaya Matematika, Tome 18 (2006) no. 1, pp. 146-155. http://geodesic.mathdoc.fr/item/DM_2006_18_1_a10/
@article{DM_2006_18_1_a10,
     author = {E. V. Sadovnik},
     title = {Testing numbers of the form $N=2kp^m-1$ for primality},
     journal = {Diskretnaya Matematika},
     pages = {146--155},
     year = {2006},
     volume = {18},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2006_18_1_a10/}
}
TY  - JOUR
AU  - E. V. Sadovnik
TI  - Testing numbers of the form $N=2kp^m-1$ for primality
JO  - Diskretnaya Matematika
PY  - 2006
SP  - 146
EP  - 155
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DM_2006_18_1_a10/
LA  - ru
ID  - DM_2006_18_1_a10
ER  - 
%0 Journal Article
%A E. V. Sadovnik
%T Testing numbers of the form $N=2kp^m-1$ for primality
%J Diskretnaya Matematika
%D 2006
%P 146-155
%V 18
%N 1
%U http://geodesic.mathdoc.fr/item/DM_2006_18_1_a10/
%G ru
%F DM_2006_18_1_a10

Voir la notice de l'article provenant de la source Math-Net.Ru

We suggest an algorithm to test numbers of the form $N=2kp^m-1$ for primality, where $2k$, $k$ is an odd positive integer, $2k$, $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)$.

[1] Agrawal M., Kayal N., Saxena N., Primes is in P, Dept. Computer Sci. and Engineering, Indian Inst. Technology, Kanpur, Kanpur-208016, 2002

[2] Grusho A. A., Primenko E. A., Timonina E. E., Kriptograficheskie protokoly, Ioshkar-Ola, 2001 | Zbl

[3] Lucas E., “Theorie das functions numeriques simplement periodiques”, Amer. J. Math., 1 (1878), 184–239, 289–321 | DOI | MR

[4] Vinogradov I. M., Osnovy teorii chisel, Nauka, Moskva, 1972 | MR

[5] Williams H. C., “Effective primality tests for some integer of the form $A5^n-1$ and $A7^n-1$”, Mathematics of Computation, 48:177 (1987), 385–403 | DOI | MR | Zbl

[6] Devenport G., Vysshaya arifmetika. Vvedenie v teoriyu chisel, Nauka, Moskva, 1965