Новый комбинированный тест простоты натуральных чисел

Одним из перспективных направлений теории чисел является построение полиномиальных тестов простоты целых чисел. Такие тесты можно использовать в криптографии, улучшая современные протоколы шифрования. В статье \textquotedblleft О Baillie-PSW гипотезе\textquotedblright\ в 2024 г. рассмотрен комбинированный тест простоты, основанный на проверке двух условий: малой теоремы Ферма $2^{n-1}\equiv 1(\bmod\ n)$ и теоремы Люка $F_{n+1}\equiv 0(\bmod\ n)$, где $F_n$ -$n$-член ряда Фибоначчи для чисел $n\equiv\pm 2(\bmod\ 5)$. Нечетные составные числа, проходящие этот комбинированный тест, там названы FL-псевдопростыми. Были установлены жесткие ограничения на FL-псевдопростые числа и доказано их отсутствие на интервале до $10^{23}$. В данной статье рассматривается комбинация комбинацию теста Ферма с тестом простоты, построенном на эллиптических кривых над конечными полями. Предложенный тест успешно работает с нечетными числами специального вида, именно, $n\equiv 2(\bmod\ 3)$, для которых формулируется гипотеза, аналогичная Bailee-PSW гипотезе.

1. Washington L. Elliptic curves: number theory and cryptography, 2nd edition, Discr. Math. Appl. Series, Editor Kenneth H. Rosen.

2. Ишмухаметов Ш.Т., Антонов Н.А., Мубараков Б.Г., Рубцова Р.Г. Об одном комбинированном тесте простоты, Изв. вузов. Матем. (12), 123–129 (2022).

3. Ишмухаметов Ш.Т., Мубараков Б.Г., Рубцова Р.Г., Олейникова Е.В. О Baillie-PSW гипотезе, Изв. вузов. Матем. (4), 80–88 (2024).

4. Baillie-PSW primality test, Wikipedia. https://en.wikipedia.org/wiki/Baillie-PSW_primality_test.