Processing math: 26%

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

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

Алгоритм


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

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

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



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

 Альтернативный метод поиска стартового значения u_0 дан в 1994 году.Метод много проще использованного Ризелем для случая, когда 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). При 3 ∤k (k не делится на 3)можно использовать значение P=4 и предварительный поиск не нужен.Начальное значение u_0 тогда равно последовательности Люка V_k(P, Q)по модулю 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\textsuperscripti-ый элемент последовательности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é) модифицировалпрограмму, чтобы можно было проверять простоту числа через интернет.Программа может использоваться как для индивидуального поиска, но такжевключена в некоторые проекты распределенных вычислений, включая RieselSieve и PrimeGrid.