Введение
Проверка, является ли число Мерсена простым.
Тест Лукаса — Лемера, который применим только к числам Мерсена.
the Lucas–Lehmer test that applies only to Mersenne numbers
В математике тест Лукаса — Лемера (LLT) — это тест на простоту для чисел Мерсена. Тест был первоначально разработан Эдуардом Лукасом в 1878 году и впоследствии доказан Дерриком Генри Лемером в 1930 году.
Альтернативные исходные значения
Начальные значения s0, отличные от 4, возможны, например, 10, 52 и другие. Остаток Лукаса — Лемера, вычисленный с использованием этих альтернативных начальных значений, все равно будет равен нулю, если Mp является простым числом Мерсена. Однако члены последовательности будут отличаться, и ненулевой остаток Лукаса — Лемера для непростого Mp будет иметь другое числовое значение, чем ненулевое значение, рассчитанное при s0 = 4. Также можно использовать начальное значение (2 mod Mp)(3 mod Mp)−1, которое обычно обозначается как 2/3 для краткости. Это начальное значение часто использовалось, когда это было уместно, в эпоху ручных вычислений, в том числе Лукасом при доказательстве простоты M127. Первые несколько членов последовательности: 3, 7, 47.
Знак предпоследнего срока
Если sp−2 = 0 mod Mp, то предпоследний член sp−3 = ± 2(p+1)/2 mod Mp. Знак этого предпоследнего члена называется символом Лемера ε(s0, p). В 2000 году С. Я. Гебре Эгзиябхер доказал, что для начального значения 2/3 и для p ≠ 5 знак равен: то есть ε(2/3, p) = +1, если p = 1 (mod 4) и p ≠ 5. Еще более эффективный алгоритм умножения, алгоритм Фюрера, требует времени только для умножения двух p-битовых чисел. Для сравнения, наиболее эффективный рандомизированный тест простоты для общих целых чисел, тест простоты Миллера — Рэбина, требует O(k n2 log n log log n) битовых операций с использованием умножения БПФ для n-значного числа, где k — число итераций и связано с вероятностью ошибки. При постоянном k это относится к тому же классу сложности, что и тест Лукаса — Лемера. Однако на практике стоимость выполнения большого числа итераций и другие различия приводят к более низкой производительности теста Миллера — Рэбина. Наиболее эффективный детерминированный тест простоты для любого n-значного числа, тест простоты AKS, требует Õ(n6) битовых операций в его лучшем известном варианте и остается чрезвычайно медленным даже для относительно небольших значений.
That is, ϵ(2/3, p) = +1 if p = 1 (mod 4) and p ≠ 5. An even more efficient multiplication algorithm, Fürer's algorithm, only needs time to multiply two p bit numbers. By comparison, the most efficient randomized primality test for general integers, the Miller–Rabin primality test, requires O(k n2 log n log log n) bit operations using FFT multiplication for an n digit number, where k is the number of iterations and is related to the error rate. For constant k, this is in the same complexity class as the Lucas Lehmer test. In practice however, the cost of doing many iterations and other differences leads to worse performance for Miller–Rabin. The most efficient deterministic primality test for any n digit number, the AKS primality test, requires Õ(n6) bit operations in its best known variant and is extremely slow even for relatively small values.
Приложения
Тест Лукаса — Лемера является одним из основных тестов на простоту, используемых проектом Great Internet Mersenne Prime Search (GIMPS) для обнаружения больших простых чисел. Этот проект успешно обнаружил многие из самых больших простых чисел, известных на сегодняшний день. Тест считается ценным, поскольку позволяет достоверно проверять большое количество очень больших чисел на простоту за разумное время. В отличие от него, эквивалентно быстрый тест Пепина для любого числа Ферма может быть применен лишь к гораздо меньшему набору очень больших чисел до достижения вычислительных ограничений.