Русская Википедия:Тест Люка — Лемера — Ризеля
Тест Люка — Лемера — Ризеля (LLR) — тест простоты для чисел вида <math>N = k \cdot 2^n-1</math> с <math>2^n > k</math> (подмножество <math>3 \cdot 2^n - 1</math> таких чисел называется числами Сабита). Разработан Хансом Ризелем и базируется на тесте Люка — Лемера, является самым быстрым детерминированным алгоритмом для чисел такого вида[1].
Алгоритм
Алгоритм очень похож на тест Люка — Лемера, но начинается со значения, зависящего от <math>k</math>. Для алгоритма используется последовательность Люка <math>\{u_i\}</math>, задаваемая для <math>i>0</math> формулой:
- <math>u_i = u_{i-1}^2-2</math>.
<math>N</math> является простым в том и только в том случае, когда оно делит <math>u_{n-2}</math>.
Поиск стартового значения
- Случай <math>k = 1</math>. Если <math>n</math> — нечётно, то берётся значение <math>u_0 = 4</math>. Если <math>n \equiv 3 \pmod 4</math>, то берётся <math>u_0 = 3</math>. Для простого <math>n</math> — это числа Мерсенна.
- Случай <math>k = 3</math>. Значение <math>u_0 = 5778</math> можно использовать для всех <math>n \equiv 0, 3 \pmod 4</math>n ≡ 0, 3 (mod 4).
- Если <math>k \equiv 1,5 \pmod 6</math> и <math>N</math> не делится на 3, можно использовать значение <math>u_0 = (2+\sqrt{3})^k+(2-\sqrt{3})^k</math>.
- В остальных случаях <math>k</math> делится на 3 и выбрать правильное стартовое значение u0 значительно труднее.
Альтернативный метод поиска стартового значения <math>u_0</math> дан в 1994 годуШаблон:Sfn. Метод много проще использованного Ризелем для случая, когда 3 делит <math>k</math>. В альтернативном способе сначала находится значение <math>P</math>, удовлетворяющее следующему равенству символов Якоби:
- <math>\left(\frac{P-2}{N}\right)=1</math> и <math>\left(\frac{P+2}{N}\right)=-1</math>.
На практике нужно проверить лишь несколько значений <math>P</math> (5, 8, 9 или 11 перекрывают 85 %).
Чтобы получить начальное значение <math>u_0</math> из <math>P</math> можно использовать последовательность Люка <math>(P,1)</math>Шаблон:SfnШаблон:Sfn. При 3 ∤k (k не делится на 3) можно использовать значение <math>P=4</math> и предварительный поиск не нужен. Начальное значение <math>u_0</math> тогда равно последовательности Люка <math>V_k(P, 1)</math> по модулю <math>N</math>. Этот процесс занимает очень малое время по сравнению с основным тестом.
Механизм теста
Тест Люка — Лемера — Ризеля является частным случаем проверки простоты порядка группы. В тесте показывается, что некоторое число — простое в связи с тем, что некоторая группа имеет порядок, который был бы равен этому простому числу, для чего выявляется элемент группы, имеющий в точности нужный порядок.
В тестах, подобных тестам Люка, для числа <math>N</math> используется мультипликативная группа квадратичного расширения целых по модулю <math>N</math>. Если <math>N</math> — простое, порядок мультипликативной группы равен <math>N^2-1</math>, и она имеет подгруппу порядка <math>N+1</math>, для целей теста ищется порождающее множество этой подгруппы.
Можно найти неитеративное выражение для <math>u_i</math>. Следуя модели теста Люка — Лемера, положим <math>u_i = a^{2^i} + a^{-2^i}</math> и получим по индукции <math>u_i = u_{i-1}^2 - 2</math>.
Рассмотрим 2i-ый элемент последовательности <math>v(i) = a^i + a^{-i}</math>. Если a удовлетворяет квадратному уравнению, это последовательность Люка, и она подчиняется выражению <math>v(i) = \alpha v(i-1) + \beta v(i-2)</math>. В действительности мы ищем <math>k \times 2^i</math>-ый элемент другой последовательности, но поскольку при децимации (выборка каждого k-го элемента) последовательности Люка получаем также последовательность Люка, мы можем выбирать множитель k путём выбора стартовой точки.
LLR программа
LLR — это программа, которая выполняет LLR-тест. Программа разработана Жаном Пене (Jean Penné). Винсент Пене (Vincent Penné) модифицировал программу, чтобы можно было проверять простоту числа через интернет. Программа может использоваться как для индивидуального поиска, но также включена в некоторые проекты распределенных вычислений, включая Riesel Sieve и PrimeGrid.
См. также
Примечания
Литература
Ссылки
- Download Jean Penné's LLR
- Math::Prime::Util::GMP — Модуль на Perl, базовая реализация LLR и теста Прота, а также некоторые методы из статьи Брилхарта, Лемера и Селфриджа.
- ↑ Для проверки простоты похожих на эти чисел Прота — <math>N = k \cdot 2^n+1</math> используется либо Теорема Прота (вероятностный алгоритм), либо один из детерминированных алгоритмов, описанных Брилхартом, Лемером и Селфриджом в 1975 году — см. Шаблон:Harvnb
