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

Тест Люка — Лемера — Ризеля (LLR) — тест простоты для чисел вида [math]\displaystyle{ N = k \cdot 2^n-1 }[/math] с [math]\displaystyle{ 2^n \gt k }[/math] (подмножество [math]\displaystyle{ 3 \cdot 2^n - 1 }[/math] таких чисел называется числами Сабита). Разработан Хансом Ризелем и базируется на тесте Люка — Лемера, является самым быстрым детерминированным алгоритмом для чисел такого вида.

Алгоритм

Алгоритм очень похож на тест Люка — Лемера, но начинается со значения, зависящего от [math]\displaystyle{ k }[/math]. Для алгоритма используется последовательность Люка [math]\displaystyle{ \{u_i\} }[/math], задаваемая для [math]\displaystyle{ i\gt 0 }[/math] формулой:

[math]\displaystyle{ u_i = u_{i-1}^2-2 }[/math].

[math]\displaystyle{ N }[/math] является простым в том и только в том случае, когда оно делит [math]\displaystyle{ u_{n-2} }[/math].

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

• Случай [math]\displaystyle{ k = 1 }[/math]. Если [math]\displaystyle{ n }[/math] — нечётно, то берётся значение [math]\displaystyle{ u_0 = 4 }[/math]. Если [math]\displaystyle{ n \equiv 3 \pmod 4 }[/math], то берётся [math]\displaystyle{ u_0 = 3 }[/math]. Для простого [math]\displaystyle{ n }[/math] — это числа Мерсенна.
• Случай [math]\displaystyle{ k = 3 }[/math]. Значение [math]\displaystyle{ u_0 = 5778 }[/math] можно использовать для всех [math]\displaystyle{ n \equiv 0, 3 \pmod 4 }[/math]n ≡ 0, 3 (mod 4).
• Если [math]\displaystyle{ k \equiv 1,5 \pmod 6 }[/math] и [math]\displaystyle{ N }[/math] не делится на 3, можно использовать значение [math]\displaystyle{ u_0 = (2+\sqrt{3})^k+(2-\sqrt{3})^k }[/math].
• В остальных случаях [math]\displaystyle{ k }[/math] делится на 3 и выбрать правильное стартовое значение u₀ значительно труднее.

Альтернативный метод поиска стартового значения [math]\displaystyle{ u_0 }[/math] дан в 1994 году. Метод много проще использованного Ризелем для случая, когда 3 делит [math]\displaystyle{ k }[/math]. В альтернативном способе сначала находится значение [math]\displaystyle{ P }[/math], удовлетворяющее следующему равенству символов Якоби:

[math]\displaystyle{ \left(\frac{P-2}{N}\right)=1 }[/math] и [math]\displaystyle{ \left(\frac{P+2}{N}\right)=-1 }[/math].

На практике нужно проверить лишь несколько значений [math]\displaystyle{ P }[/math] (5, 8, 9 или 11 перекрывают 85 %).

Чтобы получить начальное значение [math]\displaystyle{ u_0 }[/math] из [math]\displaystyle{ P }[/math] можно использовать последовательность Люка [math]\displaystyle{ (P,1) }[/math]. При 3 ∤k (k не делится на 3) можно использовать значение [math]\displaystyle{ P=4 }[/math] и предварительный поиск не нужен. Начальное значение [math]\displaystyle{ u_0 }[/math] тогда равно последовательности Люка [math]\displaystyle{ V_k(P, 1) }[/math] по модулю [math]\displaystyle{ N }[/math]. Этот процесс занимает очень малое время по сравнению с основным тестом.

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

Тест Люка — Лемера — Ризеля является частным случаем проверки простоты порядка группы. В тесте показывается, что некоторое число — простое в связи с тем, что некоторая группа имеет порядок, который был бы равен этому простому числу, для чего выявляется элемент группы, имеющий в точности нужный порядок.

В тестах, подобных тестам Люка, для числа [math]\displaystyle{ N }[/math] используется мультипликативная группа квадратичного расширения целых по модулю [math]\displaystyle{ N }[/math]. Если [math]\displaystyle{ N }[/math] — простое, порядок мультипликативной группы равен [math]\displaystyle{ N^2-1 }[/math], и она имеет подгруппу порядка [math]\displaystyle{ N+1 }[/math], для целей теста ищется порождающее множество этой подгруппы.

Можно найти неитеративное выражение для [math]\displaystyle{ u_i }[/math]. Следуя модели теста Люка — Лемера, положим [math]\displaystyle{ u_i = a^{2^i} + a^{-2^i} }[/math] и получим по индукции [math]\displaystyle{ u_i = u_{i-1}^2 - 2 }[/math].

Рассмотрим 2ⁱ-ый элемент последовательности [math]\displaystyle{ v(i) = a^i + a^{-i} }[/math]. Если a удовлетворяет квадратному уравнению, это последовательность Люка, и она подчиняется выражению [math]\displaystyle{ v(i) = \alpha v(i-1) + \beta v(i-2) }[/math]. В действительности мы ищем [math]\displaystyle{ k \times 2^i }[/math]-ый элемент другой последовательности, но поскольку при децимации (выборка каждого k-го элемента) последовательности Люка получаем также последовательность Люка, мы можем выбирать множитель k путём выбора стартовой точки.

LLR программа

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

См. также

• Числа Ризеля

Литература

• Hans Riesel. Lucasian Criteria for the Primality of N = h•2ⁿ − 1 // Mathematics of Computation. — American Mathematical Society, 1969. — Т. 23, вып. 108. — С. 869—875. — doi:10.2307/2004975. — .
• John Brillhart, Derrick Henry Lehmer, John Selfridge. New Primality Criteria and Factorizations of 2^m ± 1 // Mathematics of Computation. — 1975. — Vol. 29. — Вып. 130. — С. 620—647. — doi:10.1090/S0025-5718-1975-0384673-1.
• Öystein J. Rödseth. A note on primailty tests for N=h•2^n−1 // BIT Numerical Mathematics. — 1994. — Т. 34, вып. 3. — С. 451—454. — doi:10.1007/BF01935653. Архивировано 4 марта 2016 года.
• Hans Riesel. Prime Numbers and Computer Methods for Factorization. — 2nd. — Birkhäuser, 1994. — Т. 126. — С. 107—121. — (Progress in Mathematics). — ISBN 0-8176-3743-5.

Ссылки

• Download Jean Penné's LLR
• Math::Prime::Util::GMP — Модуль на Perl, базовая реализация LLR и теста Прота, а также некоторые методы из статьи Брилхарта, Лемера и Селфриджа.