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.
UDC:
511.1 Received: 25.12.2023
Revised: 25.12.2023
Accepted: 26.12.2023
DOI:
10.26907/0021-3446-2024-4-80-88