КФУ. Карточка публикации. Об одном комбинированном тесте простоты

КАЗАНСКИЙ
ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

RUS

- EN
- 中文
- ES

ОБ ОДНОМ КОМБИНИРОВАННОМ ТЕСТЕ ПРОСТОТЫ

Форма представления

Статьи в российских журналах и сборниках

Год публикации

2022

Язык

русский

Авторы, сотрудники КФУ

Ишмухаметов Шамиль Талгатович, автор

Мубараков Булат Газинурович, автор

Рубцова Рамиля Гакилевна, автор

Авторы, аспиранты КФУ

Антонов Николай Андреевич, автор

Библиографическое описание на языке оригинала

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

Аннотация

Рассматривается комбинированный алгоритм проверки простоты натуральных чисел, состоящий из теста Лукаса и проверки условия Ферма 2n−1≡1(mod n). Назовем такую процедуру L2-тестом. Составные числа, проходящие L2-тест, называются L2-псевдопростыми. Мы дадим описание нового эффективного алгоритма поиска L2-псевдопростых чисел, с помощью которого покажем, что не существует L2-псевдопростых чисел n вида n≡?2(mod5), меньших B=1023 (эта граница достигнута на сегодняшний день и она постоянно повышается). Таким образом, L2-тест является детерминированным тестом, позволяющим определить простоту натуральных чисел n≡?2(mod5) как минимум до 1023 всего за две итерации, каждая из которых имеет вычислительную сложность O(ln3n).

Ключевые слова

тест простоты Лукаса, тест Ферма, вероятностный тест простоты, детерминированный тест простоты.

Название журнала

Известия ВУЗов, Математика

Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку

https://repository.kpfu.ru/?p_id=284450

Полная запись метаданных

Поле DC	Значение	Язык
dc.contributor.author	Ишмухаметов Шамиль Талгатович	ru_RU
dc.contributor.author	Мубараков Булат Газинурович	ru_RU
dc.contributor.author	Рубцова Рамиля Гакилевна	ru_RU
dc.contributor.author	Антонов Николай Андреевич	ru_RU
dc.date.accessioned	2022-01-01T00:00:00Z	ru_RU
dc.date.available	2022-01-01T00:00:00Z	ru_RU
dc.date.issued	2022	ru_RU
dc.identifier.citation	Ш.Т.Ишмухаметов, Н.А.Антонов, Б.Г.Мубараков, Р.Г.Рубцова. Об одном комбинированном тесте простоты// Известия вузов.Матем., 2022, номер 12, с.123–129	ru_RU
dc.identifier.uri	https://repository.kpfu.ru/?p_id=284450	ru_RU
dc.description.abstract	Известия ВУЗов, Математика	ru_RU
dc.description.abstract	Рассматривается комбинированный алгоритм проверки простоты натуральных чисел, состоящий из теста Лукаса и проверки условия Ферма 2n−1≡1(mod n). Назовем такую процедуру L2-тестом. Составные числа, проходящие L2-тест, называются L2-псевдопростыми. Мы дадим описание нового эффективного алгоритма поиска L2-псевдопростых чисел, с помощью которого покажем, что не существует L2-псевдопростых чисел n вида n≡?2(mod5), меньших B=1023 (эта граница достигнута на сегодняшний день и она постоянно повышается). Таким образом, L2-тест является детерминированным тестом, позволяющим определить простоту натуральных чисел n≡?2(mod5) как минимум до 1023 всего за две итерации, каждая из которых имеет вычислительную сложность O(ln3n).	ru_RU
dc.language.iso	ru	ru_RU
dc.subject	тест простоты Лукаса	ru_RU
dc.subject	тест Ферма	ru_RU
dc.subject	вероятностный тест простоты	ru_RU
dc.subject	детерминированный тест простоты.	ru_RU
dc.title	Об одном комбинированном тесте простоты	ru_RU
dc.type	Статьи в российских журналах и сборниках	ru_RU