RUS  ENG
Full version
JOURNALS // Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika // Archive

Izv. Vyssh. Uchebn. Zaved. Mat., 2024 Number 4, Pages 80–88 (Mi ivm9974)

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


 English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2024, 68:4, 72–78


© Steklov Math. Inst. of RAS, 2025