Processing math: 100%

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

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

Алгоритм


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

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

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



  • Случай k=1. Если n — нечётно, то берётся значение u0=4. Если n3(mod4), то берётся u0=3. Для простого n — это числа Мерсенна.
  • Случай k=4. Значение u0=5778 можно использовать для всех n0,3(mod4)n ≡ 0, 3 (mod 4).
  • Если k1,5(mod6) и N не делится на 3, можно использовать значение u0=(2+3)k+(23)k.
  • В остальных случаях k делится на 3 и выбрать правильное стартовое значение u0 значительно труднее.

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

(P2N)=1 и (P+2N)=1.
 На практике нужно проверить лишь несколько значений P (5, 8, 9 или 11перекрывают 85 Чтобы получить начальное значение u0 из P можно использоватьпоследовательность Люка (P,1). При 3 ∤k (k не делится на 3)можно использовать значение P=4 и предварительный поиск не нужен.Начальное значение u0 тогда равно последовательности Люка Vk(P,Q)по модулю N. Этот процесс занимает очень малое время по сравнению сосновным тестом.

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


 Тест Люка — Лемера — Ризеля является частным случаем проверкипростоты порядка группы. В тесте показывается, что некоторое число —простое в связи с тем, что некоторая группа имеет порядок, который былбы равен этому простому числу, для чего выявляется элемент группы,имеющий в точности нужный порядок.
 В тестах, подобных тестам Люка, для числа N используетсямультипликативная группа квадратичного расширения целых по модулю N.Если N — простое, порядок мультипликативной группы равен N21, иона имеет подгруппу порядка N+1, для целей теста ищется порождающеемножество этой подгруппы.
 Можно найти неитеративное выражение для ui. Следуя модели тестаЛюка — Лемера, положим ui=a2i+a2i и получим поиндукции ui=u2i12.
 Рассмотрим 2i-ый элемент последовательностиv(i)=ai+ai. Если a удовлетворяет квадратномууравнению, это последовательность Люка, и она подчиняется выражениюv(i)=αv(i1)+βv(i2). В действительности мы ищемk×2i-ый элемент другой последовательности, но поскольку придецимации (выборка каждого k-го элемента) последовательности Люкаполучаем также последовательность Люка, мы можем выбирать множительk путём выбора стартовой точки.

LLRпрограмма


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