Вычислительные методы в дискретной математике

Построение сильных псевдопростых чисел Кармайкла, проходящих тест Миллера — Рабина по многим первым простым основаниям

Ю. Ф. Болтнев


Аннотация: Описан алгоритм построения сильных псевдопростых чисел Кармайкла, которые проходят тест Миллера — Рабина по многим первым простым основаниям. Найдены явные формулы для вычисления всех таких простых модулей $p$, что фиксированное $b$ — квадратичный невычет по модулю $p$. Даны оценки нижней границы для построенных чисел Кармайкла. Программа, реализующая разработанный алгоритм, позволила построить сильное псевдопростое число Кармайкла длиной 3 055 цифр, которое проходит тест Миллера — Рабина по всем целым основаниям, меньшим 2 371, что значительно превосходит полученные ранее результаты.

Ключевые слова: сильное псевдопростое число, число Кармайкла, тест Миллера — Рабина.

УДК: 511.172

DOI: 10.17223/2226308X/18/55