О Baillie-PSW гипотезе

Аннотация

Baillie PSW-гипотеза была сформулирована в 1980 году и получила название по именам авторов (R. Baillie, C. Pomerance, J. Selfridge и S.Wagstaff). Гипотеза связана с проблемой существования нечетных чисел n \equiv \pm 2 (mod 5), являющихся одновременно Фермаи Лукас-псевдопростыми (кратко, FL-псевдопростыми). Ферма псевдопростым по базе a называется составное число n, удовлетворяющее условию an 1 \equiv 1 (mod n). База a выбирается равной 2. Псевдопростое по Лукасу это составное n, удовлетворяющее Fn e(n) \equiv 0 (mod n), где e(n) — символ Лежандра e(n) = \bigl( n 5 \bigr) , Fm — m-й член ряда Фибоначчи. Согласно Baillie PSW-гипотезе FL-псевдопростых чисел не существует. Если гипотеза верна, то комбинированный тест простоты, проверяющий условия Ферма и Лукаса для нечетных чисел, не делящихся на 5, дает верный ответ для всех чисел вида n \equiv \pm 2 (mod 5), что порождает новый детерминированный полиномиальный тест простоты, определяющий простоту шестидесяти процентов всех нечетных чисел всего за две проверки. В этой работе мы продолжили исследование FL-псевдопростых чисел, начатое в нашей статье ”Об одном комбинированном тесте простоты”, опубликованной в журнале ”Изв. вузов. Матем.” (12) за 2022, установили новые ограничения на вероятные FL-псевдопростые числа и описали новые алгоритмы проверки FL-простоты, с помощью которых доказали отсутствие таких чисел до границы B = 1021, что больше, чем в тридцать раз превышают известную ранее границу 264, найденную J. Gilchrist 2013 году. Также была исправлена неточность в
формулировке теоремы 4 упомянутой статьи.