Тест Люка Лемера Ризеля

 '''Тест Люка — Лемера — Ризеля ' (LLR'') — тест простоты для чисел вида N=k2n1 с 2n>k (подмножество 32n1 таких чисел называется числами Сабита). Разработан Хансом Ризелем и базируется на тесте Люка — Лемера, является самым быстрым детерминированным алгоритмом для чисел такого вида.

Алгоритм


 Алгоритм очень похож на тест Люка — Лемера, но начинается со значения, зависящего от k. Для алгоритма используется последовательность Люка {ui}, задаваемая для i>0 формулой:

ui=ui122.
N является простым в том и только в том случае, когда оно делит un2.

Поиск стартового значения



  • Случай k=1. Если n — нечётно, то берётся значение u0=4. Если n3(mod4), то берётся u0=3. Для простого n — это числа Мерсенна.
  • Случай k=4. Значение u0=5778 можно использовать для всех n0,3(mod4)n ≡ 0, 3 (mod 4).
  • Если k1,5(mod6) и N не делится на 3, можно использовать значение u0=(2+3)k+(23)k.
  • В остальных случаях k делится на 3 и выбрать правильное стартовое значение u0 значительно труднее.

 Альтернативный метод поиска стартового значения u0 дан в 1994 году. Метод много проще использованного Ризелем для случая, когда 3 делит k. В альтернативном способе сначала находится значение P, удовлетворяющее следующему равенству символов Якоби:

(P2N)=1 и (P+2N)=1.
  На практике нужно проверить лишь несколько значений P (5, 8, 9 или 11 перекрывают 85  Чтобы получить начальное значение u0 из P можно использовать последовательность Люка (P,1). При 3 ∤k (k не делится на 3) можно использовать значение P=4 и предварительный поиск не нужен. Начальное значение u0 тогда равно последовательности Люка Vk(P,Q) по модулю N. Этот процесс занимает очень малое время по сравнению с основным тестом.

Механизм теста


 Тест Люка — Лемера — Ризеля является частным случаем проверки простоты порядка группы. В тесте показывается, что некоторое число — простое в связи с тем, что некоторая группа имеет порядок, который был бы равен этому простому числу, для чего выявляется элемент группы, имеющий в точности нужный порядок.
 В тестах, подобных тестам Люка, для числа N используется мультипликативная группа квадратичного расширения целых по модулю N. Если N — простое, порядок мультипликативной группы равен N21, и она имеет подгруппу порядка N+1, для целей теста ищется порождающее множество этой подгруппы.
 Можно найти неитеративное выражение для ui. Следуя модели теста Люка — Лемера, положим ui=a2i+a2i и получим по индукции ui=ui122.
 Рассмотрим 2i-ый элемент последовательности v(i)=ai+ai. Если a удовлетворяет квадратному уравнению, это последовательность Люка, и она подчиняется выражению v(i)=αv(i1)+βv(i2). В действительности мы ищем k×2i-ый элемент другой последовательности, но поскольку при децимации (выборка каждого k-го элемента) последовательности Люка получаем также последовательность Люка, мы можем выбирать множитель k путём выбора стартовой точки.

LLR программа


 LLR — это программа, которая выполняет LLR-тест. Программа разработана Жаном Пене (Jean Penné). Винсент Пене (Vincent Penné) модифицировал программу, чтобы можно было проверять простоту числа через интернет. Программа может использоваться как для индивидуального поиска, но также включена в некоторые проекты распределенных вычислений, включая Riesel Sieve и PrimeGrid.