Geodesic
New probabilistic primality test
Zapiski Nauchnykh Seminarov POMI, Algebra and number theory. Part 2, Tome 479 (2019), pp. 121-130 
A. G. Moshonkin; I. M. Khamitov. New probabilistic primality test. Zapiski Nauchnykh Seminarov POMI, Algebra and number theory. Part 2, Tome 479 (2019), pp. 121-130. http://geodesic.mathdoc.fr/item/ZNSL_2019_479_a4/
@article{ZNSL_2019_479_a4,
     author = {A. G. Moshonkin and I. M. Khamitov},
     title = {New probabilistic primality test},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {121--130},
     year = {2019},
     volume = {479},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2019_479_a4/}
}
TY  - JOUR
AU  - A. G. Moshonkin
AU  - I. M. Khamitov
TI  - New probabilistic primality test
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2019
SP  - 121
EP  - 130
VL  - 479
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2019_479_a4/
LA  - ru
ID  - ZNSL_2019_479_a4
ER  - 
%0 Journal Article
%A A. G. Moshonkin
%A I. M. Khamitov
%T New probabilistic primality test
%J Zapiski Nauchnykh Seminarov POMI
%D 2019
%P 121-130
%V 479
%U http://geodesic.mathdoc.fr/item/ZNSL_2019_479_a4/
%G ru
%F ZNSL_2019_479_a4

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

In this paper we present a new general probabilistic test for primality. The estimated efficiency of our test turns out to be inferior to that of the Miller–Rabin test. However, we provide some heuristic arguments that our estimation of efficiency is quite rough. This allows us to expect that the real efficiency of our test is much greater.

[1] R. M. Robinson, “Mersenne and Fermat Numbers”, Proc. Amer. Math. Soc., 5 (1954), 842–846 | DOI | MR | Zbl

[2] M. Agrawal, N. Kayal, N. Saxena, “Primes is in $P$”, Ann. of Math. (2), 160:2 (2004), 781–793 | DOI | MR | Zbl

[3] E. Lucas, “Theorie des fonctions numeriques simplement periodiques”, Amer. J. Math., 1:2–4 (1878), 184–240 (French) ; 289–321 | DOI | MR | Zbl

[4] W. R. Alford, A. Granville, C. Pomerance, “There are infinitely many Carmichael numbers”, Ann. of Math., 139 (1994), 703–722 | DOI | MR | Zbl

[5] R. Solovay, V. Strassen, “A fast Monte-Carlo test for primality”, SIAM J. Comput., 6:1 (1977), 84–85 | DOI | MR | Zbl

[6] M. O. Rabin, “Probabilistic algorithm for testing primality”, J. Number Theory, 12:1 (1980), 128–138 | DOI | MR | Zbl

[7] M. Baker, Cipolla's algorithm for finding square roots mod p, http://people.math.gatech.edu/m̃baker/pdf/cipolla2011.pdf