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

Алгоритм

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

${\displaystyle u_{i}=u_{i-1}^{2}-2}$ .

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

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

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

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

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

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

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

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

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

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

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

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

LLR программа

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

См. также

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

Примечания

Литература

• Hans Riesel. // Mathematics of Computation. — American Mathematical Society, 1969. — Т. 23 , вып. 108 . — С. 869—875 . — doi : . — JSTOR .
• John Brillhart, Derrick Henry Lehmer, John Selfridge. // Mathematics of Computation. — 1975. — Vol. 29. — Вып. 130 . — С. 620—647 . — doi : .
• Öystein J. Rödseth. // BIT Numerical Mathematics. — 1994. — Т. 34 , вып. 3 . — С. 451—454 . — doi : . 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 .

Ссылки

• — Модуль на Perl, базовая реализация LLR и теста Прота, а также некоторые методы из статьи Брилхарта, Лемера и Селфриджа.