Geodesic
On a conbined primality test
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 12 (2022), pp. 123-129.

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

In this paper we consider a hybrid primality test consisting of checking the relation $2^{n-1}\equiv 1 (\bmod\ n)$ and the Lucas primality test. Let call this procedure as $\mathrm{L}2$-test. Composite integers passing $\mathrm{L}2$-test are called $\mathrm{L}2$-pseudoprime. In this paper we develop an effective algorithm for searching $\mathrm{L}2$-pseudoprimes of form $n\equiv\pm 2(\bmod 5)$. Using it we prove that there are no $\mathrm{L}2$-pseudoprimes of the mentioned form below $B=10^{23}$ (it is the currently reached boarder and it continues to increase). Thus, $\mathrm{L}2$-test is a deterministic test at the current interval up to $B=10^{23}$ allowing the researchers to check an odd $n\equiv\pm 2(\bmod 5)$ for primality using a polynomial two-round procedure of rate $O(\ln^3 n)$.
Keywords: Lucas primality test, the Fermat test, probabilistic primality test, deterministic primality test. 
@article{IVM_2022_12_a10,
     author = {Sh. T. Ishmukhametov and N. A. Antonov and B. G. Mubarakov and G. G. Rubtsova},
     title = {On a conbined primality test},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {123--129},
     publisher = {mathdoc},
     number = {12},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2022_12_a10/}
}
TY  - JOUR
AU  - Sh. T. Ishmukhametov
AU  - N. A. Antonov
AU  - B. G. Mubarakov
AU  - G. G. Rubtsova
TI  - On a conbined primality test
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2022
SP  - 123
EP  - 129
IS  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2022_12_a10/
LA  - ru
ID  - IVM_2022_12_a10
ER  - 
%0 Journal Article
%A Sh. T. Ishmukhametov
%A N. A. Antonov
%A B. G. Mubarakov
%A G. G. Rubtsova
%T On a conbined primality test
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2022
%P 123-129
%N 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2022_12_a10/
%G ru
%F IVM_2022_12_a10
Sh. T. Ishmukhametov; N. A. Antonov; B. G. Mubarakov; G. G. Rubtsova. On a conbined primality test. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 12 (2022), pp. 123-129. http://geodesic.mathdoc.fr/item/IVM_2022_12_a10/

[1] Alford W.R., Granville A., Pomerance C., “There are Infinitely Many Carmichael Numbers”, Ann. Math., 139:3 (1994), 703–722

[2] Crandall R., Pomerance C., Prime Numbers: A Computational Perspertive, Springer–Verlag, Berlin, 2005

[3] Ishmukhametov Sh.T., Rubtsova R.G., Khusnutdinov R.R., “Ob odnom teste prostoty naturalnykh chisel”, Izv. vuzov. Matem., 2022, no. 2, 83–87

[4] Ishmukhametov S., Antonov N., Mubarakov B., A new primality test constructed as a combination of Miller–Rabin and Lucas algorithms, MDPI Special Edition (to appear)

[5] Computational complexity of mathematical operations, Wikipedia, https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations