|
Brief communications
On the Baillie PSW-conjecture
Sh. T. Ishmukhametova, B. G. Mubarakova, G. G. Rubtsovaa, E. V. Oleynikovab a Kazan Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia
b Moscow Polytechnic University, 38 Bolshaya Semenovskaya str., Moscow, 107023 Russia
Abstract:
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.
Received: 25.12.2023 Revised: 25.12.2023 Accepted: 26.12.2023
Citation:
Sh. T. Ishmukhametov, B. G. Mubarakov, G. G. Rubtsova, E. V. Oleynikova, “On the Baillie PSW-conjecture”, Izv. Vyssh. Uchebn. Zaved. Mat., 2024, no. 4, 80–88
Linking options:
https://www.mathnet.ru/eng/ivm9974 https://www.mathnet.ru/eng/ivm/y2024/i4/p80
|
Statistics & downloads: |
Abstract page: | 54 | Full-text PDF : | 1 | References: | 12 | First page: | 9 |
|