Тест Люка — Лемера — Ризеля (LLR) — тест простоты для чисел вида с (подмножество таких чисел называется числами Сабита). Разработан Хансом Ризелем и базируется на тесте Люка — Лемера, является самым быстрым детерминированным алгоритмом для чисел такого видаДля проверки простоты похожих на эти чисел Прота — используется либо Теорема Прота (вероятностный алгоритм), либо один из детерминированных алгоритмов, описанных Брилхартом, Лемером и Селфриджом в 1975 году — см. .
Алгоритм Алгоритм очень похож на тест Люка — Лемера, но начинается со значения, зависящего от . Для алгоритма используется последовательность Люка , задаваемая для формулой:
.
является простым в том и только в том случае, когда оно делит .
Поиск стартового значения Случай . Если — нечётно, то берётся значение . Если , то берётся . Для простого — это числа Мерсенна. Случай . Значение можно использовать для всех n ≡ 0, 3 (mod 4). Если и не делится на 3, можно использовать значение . В остальных случаях делится на 3 и выбрать правильное стартовое значение u0 значительно труднее.
Альтернативный метод поиска стартового значения дан в 1994 году. Метод много проще использованного Ризелем для случая, когда 3 делит . В альтернативном способе сначала находится значение , удовлетворяющее следующему равенству символов Якоби: и .
На практике нужно проверить лишь несколько значений (5, 8, 9 или 11 перекрывают 85 %).
Чтобы получить начальное значение из можно использовать последовательность Люка . При 3 ∤k (k не делится на 3) можно использовать значение и предварительный поиск не нужен. Начальное значение тогда равно последовательности Люка по модулю . Этот процесс занимает очень малое время по сравнению с основным тестом.
Механизм теста Тест Люка — Лемера — Ризеля является частным случаем проверки простоты порядка группы. В тесте показывается, что некоторое число — простое в связи с тем, что некоторая группа имеет порядок, который был бы равен этому простому числу, для чего выявляется элемент группы, имеющий в точности нужный порядок.
В тестах, подобных тестам Люка, для числа используется мультипликативная группа квадратичного расширения целых по модулю . Если — простое, порядок мультипликативной группы равен , и она имеет подгруппу порядка , для целей теста ищется порождающее множество этой подгруппы.
Можно найти неитеративное выражение для . Следуя модели теста Люка — Лемера, положим и получим по индукции .
Рассмотрим 2i-ый элемент последовательности . Если a удовлетворяет квадратному уравнению, это последовательность Люка, и она подчиняется выражению . В действительности мы ищем -ый элемент другой последовательности, но поскольку при децимации (выборка каждого k-го элемента) последовательности Люка получаем также последовательность Люка, мы можем выбирать множитель k путём выбора стартовой точки.
LLR программа LLR — это программа, которая выполняет LLR-тест. Программа разработана Жаном Пене (Jean Penné). Винсент Пене (Vincent Penné) модифицировал программу, чтобы можно было проверять простоту числа через интернет. Программа может использоваться как для индивидуального поиска, но также включена в некоторые проекты распределенных вычислений, включая Riesel Sieve и PrimeGrid.
См. также Числа Ризеля
Примечания
Литература
Ссылки Download Jean Penné's LLR Math::Prime::Util::GMP — Модуль на Perl, базовая реализация LLR и теста Прота, а также некоторые методы из статьи Брилхарта, Лемера и Селфриджа.
Категория:Тесты простоты