Geodesic
On the Baillie PSW-conjecture
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 4 (2024), pp. 80-88 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The Baillie PSW hypothesis was formulated in $1980$ and was named after the authors R. Baillie, C. Pomerance, J. Selfridge and S. Wagstaff. The hypothesis is related to the problem of the existence of odd numbers $n\equiv \pm 2\ (\bmod\ 5)$, which are both Fermat and Lucas-pseudoprimes (in short, FL-pseudoprimes). A Fermat pseudoprime to base $a$ is a composite number $n$ satisfying the condition $a^{n-1}\equiv 1\ (\bmod\ n)$. Base $a$ is chosen to be equal to $2$. A Lucas pseudoprime is a composite $n$ satisfying $F_{n-e(n)}\equiv 0\ (\bmod\ n)$, where $n(e)$ is the Legendre symbol $e(n)={n\choose 5}$, $F_m$ the $m$th term of the Fibonacci series. According to Baillie's PSW conjecture, there are no FL-pseudoprimes. If the hypothesis is true, the combined primality test checking Fermat and Lucas conditions for odd numbers not divisible by $5$ gives the correct answer for all numbers of the form $n\equiv \pm 2\ (\bmod\ 5)$, which generates a new deterministic polynomial primality test detecting the primality of $60$ percent of all odd numbers in just two checks. In this work, we continue the study of FL-pseudoprimes, started in our article "On a combined primality test" published in the journal "Izvestia VUZov.Matematika" No. $12$ in $2022$. We have established new restrictions on probable FL-pseudoprimes and described new algorithms for checking FL-primality, and with the help of them we proved the absence of such numbers up to the boundary $B=10^{21}$, which is more than $30$ times larger than the previously known boundary $2^{64}$ found by J. Gilchrist in $2013$. An inaccuracy in the formulation of theorem $4$ in the mentioned article has also been corrected.
Keywords: primality test, Lucas primality test, Fermat Small theorem, deterministic primality test. 
@article{IVM_2024_4_a7,
     author = {Sh. T. Ishmukhametov and B. G. Mubarakov and G. G. Rubtsova and E. V. Oleynikova},
     title = {On the {Baillie} {PSW-conjecture}},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {80--88},
     year = {2024},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2024_4_a7/}
}
TY  - JOUR
AU  - Sh. T. Ishmukhametov
AU  - B. G. Mubarakov
AU  - G. G. Rubtsova
AU  - E. V. Oleynikova
TI  - On the Baillie PSW-conjecture
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2024
SP  - 80
EP  - 88
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/IVM_2024_4_a7/
LA  - ru
ID  - IVM_2024_4_a7
ER  - 
%0 Journal Article
%A Sh. T. Ishmukhametov
%A B. G. Mubarakov
%A G. G. Rubtsova
%A E. V. Oleynikova
%T On the Baillie PSW-conjecture
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2024
%P 80-88
%N 4
%U http://geodesic.mathdoc.fr/item/IVM_2024_4_a7/
%G ru
%F IVM_2024_4_a7
Sh. T. Ishmukhametov; B. G. Mubarakov; G. G. Rubtsova; E. V. Oleynikova. On the Baillie PSW-conjecture. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 4 (2024), pp. 80-88. http://geodesic.mathdoc.fr/item/IVM_2024_4_a7/

[1] Baillie R., Wagstaff S.S., Jr., “Lucas Pseudoprimes (PDF)”, Math. Comp., 35:152 (1980), 1391–1417 http://mpqs.free.fr/LucasPseudoprimes.pdf | DOI | MR

[2] Pomerance C., Selfridge J.L., and Wagstaff S.S., Jr., “The Pseudoprimes to $25\cdot 10^9$”, Math. Comp., 35:151 (1980), 1003–1026 https://math.dartmouth.edu/c̃arlp/PDF/paper25.pdf | DOI | MR

[3] Crandall R., Pomerance C.B., The Prime Numbers: A Computational Perspertive, sec. ed., Springer–Verlag, Berlin, 2005 | MR

[4] Baillie–PSW primality test, Wikipedia, https://en.wikipedia.org/wiki/Baillie–PSW_primality_test

[5] Pomerance C., Are There Counterexamples to the Baillie–PSW Primality Test?, eds. H.W. Lenstra, Jr., J.K. Lenstra, and P. Van Emde Boas, Amsterdam, 1984 http://www.pseudoprime.com/dopo.pdf

[6] Baillie R., Fiori A., Wagstaff S.S., Jr., “Strengthening the Baillie-PSW primality test”, Math. Comput., 90:330 (2021), 1931–1955 | DOI | MR | Zbl

[7] Weisstein E.W., Baillie-PSW Primality Test http://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html

[8] Ishmukhametov Sh.T., Antonov N.A., Mubarakov B.G., Rubtsova R.G., “Ob odnom kombinirovannom teste prostoty”, Izv. vuzov. Matem., 2022, no. 12, 123–129 | DOI | MR

[9] Ishmukhametov S., Antonov N., Mubarakov B., “On a modification of the Lucas Primality Test”, Lobachevskii J. Math., 50:7 (2023), 1–8 | MR

[10] Wall D.D., “Fibonacci series modulo $m$”, Amer. Math. Monthly, 67:6 (1960), 525–532 | DOI | MR