Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Izv. Vyssh. Uchebn. Zaved. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2024, Number 4, Pages 80–88
DOI: https://doi.org/10.26907/0021-3446-2024-4-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
References:
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
Document Type: Article
UDC: 511.1
Language: Russian
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
Citation in format AMSBIB
\Bibitem{IshMubRub24}
\by Sh.~T.~Ishmukhametov, B.~G.~Mubarakov, G.~G.~Rubtsova, E.~V.~Oleynikova
\paper On the Baillie PSW-conjecture
\jour Izv. Vyssh. Uchebn. Zaved. Mat.
\yr 2024
\issue 4
\pages 80--88
\mathnet{http://mi.mathnet.ru/ivm9974}
\crossref{https://doi.org/10.26907/0021-3446-2024-4-80-88}
Linking options:
  • https://www.mathnet.ru/eng/ivm9974
  • https://www.mathnet.ru/eng/ivm/y2024/i4/p80
    See also
    • On a conbined primality test
      Sh. T. Ishmukhametov, N. A. Antonov, B. G. Mubarakov, G. G. Rubtsova
      Izv. Vyssh. Uchebn. Zaved. Mat., 2022:12, 123–129
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Известия высших учебных заведений. Математика Russian Mathematics (Izvestiya VUZ. Matematika)
    Statistics & downloads:
    Abstract page:54
    Full-text PDF :1
    References:12
    First page:9
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024