Тест Люка — Лемера

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Тест Люка́ — Ле́мера — эффективный тест простоты для чисел Мерсенна. Благодаря этому тесту самыми большими известными простыми числами всегда были простые числа Мерсенна, причём даже до появления компьютеров.[1]

История[править | править вики-текст]

Тест был предложен французским математиком Люка в 1878 году и дополнен американским математиком Лемером в 1930 году. Полученный тест носит имя двух ученых, которые совместно открыли его, даже не встречаясь при жизни. В 1952 году Робинсон при поддержке Лемера провел вычисления на компьютере SWAC с использованием теста Люка — Лемера, результатом которого стало открытие простых чисел и . Позднее в этом же году были открыты , и .[1]

Тест[править | править вики-текст]

Тест Люка — Лемера базируется на том наблюдении, что простота числа Мерсенна влечёт простоту числа , и следующем утверждении:

Пусть  — простое число, причем . Определим последовательность следующим образом:

Тогда  — простое тогда и только тогда, когда .


Для установления простоты последовательность чисел вычисляется по модулю числа (то есть вычисляются не сами числа , длина которых растёт экспоненциально; а остатки от деления на , длина которых ограничена q битами). Последнее число в этой последовательности называется вычетом Люка — Лемера. Таким образом, число Мерсенна является простым тогда и только тогда, когда число простое, и вычет Люка — Лемера равен нулю.

Возможными значениями являются: 4, 10, 52, 724, 970, 10084, … (последовательность A018844 в OEIS)

Вычислительная сложность[править | править вики-текст]

Вычислительная сложность теста для числа равна [2], так как в процессе выполнения теста производится возведений в квадрат и вычитаний по модулю . Длина составляет битов, причём самый простой алгоритм умножения чисел имеет сложность . Для ускорения теста следует использовать алгоритмы быстрого умножения больших целых чисел, например, метод умножения Шёнхаге — Штрассена. Сложность теста в таком случае составит .

Примеры[править | править вики-текст]

Рассмотрим выполнение теста для числа Мерсенна

Следовательно, число  — простое.

Доказательство[править | править вики-текст]

Теорема: Пусть  — простое число, причем . Определим последовательность следующим образом:

Тогда  — простое тогда и только тогда, когда .

Доказательство теоремы основано на свойствах последовательностей Люка и :

Следующие свойства доказываются по индукции:

Лемма: Пусть  — простое и , тогда справедливо следующее утверждение. Если , то .

Доказательство леммы: Положим , . Используем выше описанные свойства, чтобы получить значения для и :

, в то время как .

Таким же способом получим:

и

Иначе говоря,

и ,

откуда следует утверждение леммы, если взять .

Далее, раскроем выражение последовательностей по биному Ньютона:

Теперь, если мы положим , где  — простое число, большее 2, и учтем, что кратно за исключением тех случаев, когда и , мы получим:

, .

Если теорема Ферма утверждает, что . Поэтому , то есть . Если , то

то есть . Таким же способом получим, что , если . Мы доказали, что для любого простого числа, существует целое число такое, что .

Лемма: Если  — положительное целое число, и  — наименьшее число такое, что , то мы имеем:

тогда и только тогда, когда кратно .

Доказательство: Заметим, что последовательность совпадает с последовательностью по модулю , где число взаимно просто с , так как: .

Доказательство теоремы: По индукции имеем

.

Более того, из следует, что . Отсюда следует, что и не имеют общих нечетных делителей. Если , то для и можем записать:

Теперь, если , то должно быть делителем числа , но не должно делить , поэтому . Докажем, что . Пусть . Числа больше 3, так как нечетное и выполняется ,  — простое по условию. Используя ранее доказанные леммы, получим , где

где . Отсюда следует, что кратно . Положим ; . Так как  — четное, . Используем ранее доказанные факты и получим ; следовательно и либо . Заметим, что  — степень двойки. Отсюда следует, что и . Если  — составное, то должно быть , где и  — простые числа. Дальнейшее разложение на простые числа, если  — нечетное, невозможно, поэтому  — простое.

Наоборот, предположим, что  — простое. Покажем, что . Для этого достаточно показать, что , так как .

Так как  — простое, то биномиальный коэффициент делится на кроме тех случаев, когда или . Следовательно:

.

Здесь , поэтому по малой теореме Ферма. Наконец, используя простейший случай квадратичного закона взаимности, покажем, что , так как и . Это означает, что , так что . [3]

Псевдокод[править | править вики-текст]

Lucas–Lehmer(p)
    var s = 4
    var M = 2p — 1
    repeat p — 2 times:
        s = ((s × s) — 2) mod M
    if s = 0 return PRIME else return COMPOSITE

Модификации[править | править вики-текст]

Для чисел вида , где существует модификация данного теста, разработанная Хансом Ризелем (швед. Hans Riesel). Возможно обобщение теста для чисел вида .[4] Также существует более общий вариант — тест Люка, который применим для любого натурального числа , если известно разложение на простые множители числа .

Применения[править | править вики-текст]

Благодаря тесту Люка — Лемера простые числа Мерсенна удерживают лидерство как самые большие известные простые числа.[5] Именно тест Люка — Лемера лежит в основе проекта распределённых вычислений GIMPS, занимающегося поиском новых простых чисел Мерсенна.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 Paulo Ribenboim. The Little Book of Bigger Primes. — Springer. — 2004. — С. 78. — ISBN 978-0387201696.
  2. Eric Bach; Jeffrey Shallit. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. — The MIT Press, 1996. — С. 275. — ISBN 978-0262024051.
  3. Donald E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. — 3 (3 edition). — Addison-Wesley Professional, 1997. — С. 2. — 392 с. — ISBN 978-0201896848.
  4. H. C. Williams. A class of primality tests for trinomials which includes the Lucas-Lehmer test. (англ.). Проверено 28 ноября 2012. Архивировано из первоисточника 23 декабря 2012.
  5. The «Top Ten» Record Primes (англ.).

Литература[править | править вики-текст]