KFU. Card publication. Об одном комбинированном тесте простоты

KAZAN
FEDERAL UNIVERSITY

- RUS
- 中文
- ES

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

Form of presentation

Articles in Russian journals and collections

Year of publication

2022

Язык

русский

Authors, employees of KFU

Ishmukhametov Shamil Talgatovich, author

Mubarakov Bulat Gazinurovich, author

Rubcova Ramilya Gakilevna, author

Authors, postgraduates KFU

Antonov Nikolay Andreevich, postgraduate kfu

Bibliographic description in the original language

Sh.T.Ishmukhametov, N.A.Antonov, B.G.Mubarakov, R.G.Rubcova. Ob odnom kombinirovannom teste prostoty// Izvestiya vuzov.Matem., 2022, nomer 12, s.123–129

Annotation

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

Keywords

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

The name of the journal

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

Please use this ID to quote from or refer to the card

https://repository.kpfu.ru/eng/?p_id=284450&p_lang=2

Full metadata record

Field DC	Value	Language
dc.contributor.author	Ishmukhametov Shamil Talgatovich	ru_RU
dc.contributor.author	Mubarakov Bulat Gazinurovich	ru_RU
dc.contributor.author	Rubcova Ramilya Gakilevna	ru_RU
dc.contributor.author	Antonov Nikolay Andreevich	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/eng/?p_id=284450&p_lang=2	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	Articles in Russian journals and collections	ru_RU