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

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

Алгоритм

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

$u_i=u_{i-1}^2-2$.

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

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

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

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

$\left(\frac{P-2}{N}\right)=1$ и $\left(\frac{P+2}{N}\right)=-1$.

На практике нужно проверить лишь несколько значений $P$ (5, 8, 9 или 11 перекрывают 85 %).

Чтобы получить начальное значение $u_0$ из $P$ можно использовать последовательность Люка $(P,1)$Шаблон:SfnШаблон:Sfn. При 3 ∤k (k не делится на 3) можно использовать значение $P=4$ и предварительный поиск не нужен. Начальное значение $u_0$ тогда равно последовательности Люка $V_k(P,1)$ по модулю $N$. Этот процесс занимает очень малое время по сравнению с основным тестом.

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

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

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

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

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

LLR программа

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

См. также

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга

Ссылки

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