В математике тест Люка-Лемера-Ризеля — это тест на простоту чисел вида N = k ⋅ 2 n − 1 ( числа Ризеля ) с нечетным k < 2 n . Тест был разработан Гансом Ризелем и основан на тесте простоты Лукаса-Лемера . Это самый быстрый детерминированный алгоритм, известный для чисел такой формы. [ нужна цитата ] Для чисел вида N = k ⋅ 2 n + 1 ( числа Прота ) либо применение теоремы Прота ( алгоритм Лас-Вегаса ), либо одно из детерминированных доказательств, описанных в книге Брилхарта-Лемера-Селфриджа 1975 [1] (см. тест на простоту Поклингтона ).
Алгоритм очень похож на тест Лукаса-Лемера , но с переменной начальной точкой, зависящей от значения k .
Альтернативный метод поиска начального значения u 0 приведен в Rödseth 1994. [2] Метод выбора намного проще, чем тот, который использовал Ризель для случая, когда k делится на 3 . Сначала найдите значение P , которое удовлетворяет следующим равенствам символов Якоби :
На практике необходимо проверить лишь несколько значений P , прежде чем будет найдено одно (5, 8, 9 или 11 работают примерно в 85% испытаний). [ нужна ссылка ]
Чтобы найти начальное значение u 0 по значению P , мы можем использовать последовательность Lucas(P,1), как показано в [2] , а также на стр. 124. [3] Последнее объясняет, что когда 3 ∤ k , P =4 можно использовать, как указано выше, и дальнейший поиск не требуется.
Начальным значением u0 будет член последовательности Люка Vk ( P , 1), взятый по модулю N. Этот процесс отбора занимает очень мало времени по сравнению с основным тестом.