|
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≡±2 (mod 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 an−1≡1 (mod n). Base a is chosen to be equal to 2. A Lucas pseudoprime is a composite n satisfying Fn−e(n)≡0 (mod n), where n(e) is the Legendre symbol e(n)={n\choose 5}, F_m the mth 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: | 109 | Full-text PDF : | 1 | References: | 28 | First page: | 15 |
|