Форма представления | Статьи в российских журналах и сборниках |
Год публикации | 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 |
|