Аннотация:
Рассматривается комбинированный алгоритм проверки простоты натуральных чисел, состоящий из теста Лукаса и проверки условия Ферма $2^{n-1}\equiv 1 (\bmod\ n)$. Назовем такую процедуру $\mathrm{L}2$-тестом. Составные числа, проходящие $\mathrm{L}2$-тест, называются $\mathrm{L}2$-псевдопростыми. Мы дадим описание нового эффективного алгоритма поиска $\mathrm{L}2$-псевдопростых чисел, с помощью которого покажем, что не существует $\mathrm{L}2$-псевдопростых чисел $n$ вида $n\equiv\pm 2(\bmod 5)$, меньших $B=10^{23}$ (эта граница достигнута на сегодняшний день и она постоянно повышается).
Таким образом, $\mathrm{L}2$-тест является детерминированным тестом, позволяющим определить простоту натуральных чисел $n\equiv\pm 2(\bmod 5)$ как минимум до $10^{23}$ всего за две итерации, каждая из которых имеет вычислительную сложность $O(\ln^3 n)$.
Ключевые слова:тест простоты Лукаса, тест Ферма, вероятностный тест простоты, детерминированный тест простоты.
УДК:
510.1
Поступила: 17.11.2022 Исправленный вариант: 17.11.2022 Принята к публикации: 21.12.2022