Главная
Новости
Строительство
Ремонт
Дизайн и интерьер
Полезные советы



















Яндекс.Метрика





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

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

Алгоритм

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

u i = u i − 1 2 − 2 {displaystyle u_{i}=u_{i-1}^{2}-2} .

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

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

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

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

( P − 2 N ) = 1 {displaystyle left({frac {P-2}{N}} ight)=1} и ( P + 2 N ) = − 1 {displaystyle left({frac {P+2}{N}} ight)=-1} .

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

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

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

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

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

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

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

LLR программа

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


Имя:*
E-Mail:
Комментарий: