Открыть главное меню

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

Тест Люка — Лемера — Ризеля (LLR) — тест простоты для чисел вида с (подмножество таких чисел называется числами Сабита). Разработан Хансом Ризелем и базируется на тесте Люка — Лемера, является самым быстрым детерминированным алгоритмом для чисел такого вида[1].

АлгоритмПравить

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

 .

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

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

  • Случай  . Если   — нечётно, то берётся значение  . Если  , то берётся  . Для простого   — это числа Мерсенна.
  • Случай  . Значение   можно использовать для всех  n ≡ 0, 3 (mod 4).
  • Если   и   не делится на 3, можно использовать значение  .
  • В остальных случаях   делится на 3 и выбрать правильное стартовое значение u0 значительно труднее.

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

  и  .

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

Чтобы получить начальное значение   из   можно использовать последовательность Люка  [2][3]. При 3 ∤k (k не делится на 3) можно использовать значение   и предварительный поиск не нужен. Начальное значение   тогда равно последовательности Люка   по модулю  . Этот процесс занимает очень малое время по сравнению с основным тестом.

Механизм тестаПравить

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

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

Можно найти неитеративное выражение для  . Следуя модели теста Люка — Лемера, положим   и получим по индукции  .

Рассмотрим 2i-ый элемент последовательности  . Если a удовлетворяет квадратному уравнению, это последовательность Люка, и она подчиняется выражению  . В действительности мы ищем  -ый элемент другой последовательности, но поскольку при децимации (выборка каждого k-го элемента) последовательности Люка получаем также последовательность Люка, мы можем выбирать множитель k путём выбора стартовой точки.

LLR программаПравить

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

См. такжеПравить

ПримечанияПравить

  1. Для проверки простоты похожих на эти чисел Прота —   используется либо Теорема Прота (вероятностный алгоритм), либо один из детерминированных алгоритмов, описанных Брилхартом, Лемером и Селфриджом в 1975 году — см. Brillhart, Lehmer, Selfridge, 1975
  2. 1 2 Rödseth, 1994.
  3. Riesel, 1994, p. 194.

ЛитератураПравить

  • Hans Riesel. Lucasian Criteria for the Primality of N = h•2n − 1 // Mathematics of Computation. — American Mathematical Society, 1969. — Т. 23, вып. 108. — С. 869—875. — DOI:10.2307/2004975.
  • John Brillhart, Derrick Henry Lehmer, John Selfridge. New Primality Criteria and Factorizations of 2^m ± 1 // Mathematics of Computation. — 1975. — Vol. 29. — Вып. 130. — С. 620—647. — DOI:10.1090/S0025-5718-1975-0384673-1.
  • Öystein J. Rödseth. A note on primailty tests for N=h•2^n−1 // BIT Numerical Mathematics. — 1994. — Т. 34, вып. 3. — С. 451—454. — DOI:10.1007/BF01935653.
  • Hans Riesel. Prime Numbers and Computer Methods for Factorization. — 2nd. — Birkhäuser, 1994. — Т. 126. — С. 107—121. — (Progress in Mathematics). — ISBN 0-8176-3743-5.

СсылкиПравить

  • Download Jean Penné's LLR
  • Math::Prime::Util::GMP — Модуль на Perl, базовая реализация LLR и теста Прота, а также некоторые методы из статьи Брилхарта, Лемера и Селфриджа.