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

Те́ст Люка́ — Ле́мера (, сокр. LLT) — полиномиальный, детерминированный и безусловный (то есть не зависящий от недоказанных гипотез) тест простоты для чисел Мерсенна. Сформулирован Эдуардом Люка в 1878 году и доказан Лемером в 1930 году. 

При заданном простом числе  тест позволяет за полиномиальное время от битовой длины  числа Мерсенна  определить, является  простым или составным. Доказательство справедливости теста существенно опирается на функции Люка, что позволило обобщить тест Люка — Лемера на некоторые числа, вид которых отличен от чисел Мерсенна.

Благодаря этому тесту самыми большими известными простыми числами почти всегда были простые числа Мерсенна, причём даже до появления компьютеров; именно он лежит в основе проекта распределённых вычислений GIMPS, занимающегося поиском новых простых чисел Мерсенна. Также он интересен своей связью с чётными совершенными числами.

Формулировка 
Тест основывается на следующем критерии простоты чисел Мерсенна:

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

 LLT(p)
     ►Вход: простое нечётное число p
     S = 4
     k = 1
     M = 2p − 1
     До тех пока k != p - 1 выполнять
         S = ((S × S) − 2) mod M
         k += 1
     Конец цикла
     Если S = 0 выполнять
         Возвратить ПРОСТОЕ
     иначе
         Возвратить СОСТАВНОЕ
     Конец условия

Значения , для которых справедлив критерий простоты, образуют последовательность:  . 

Не обязательно проверять все простые нечётные  при непосредственном переборе, поскольку некоторые числа Мерсенна специального вида всегда являются составными, что следует, например, из следующей доказанной Эйлером теоремы:

Доказательство 
Один из подходов к доказательству основан на использовании функций Люка:

 

 

где  — корни квадратного уравнения

 

с дискриминантом  причём  и  взаимно просты.

В частности, при доказательстве используются некоторые свойства этих функций, а именно:

 1. 

 2. 

 3. 

 4. Если , ,  и

 ,

 то

 

 5. Если  — простое, такое, что  взаимно просто с , то  делит нацело ,

 где , а  — символ Лежандра.

Схема доказательства:

Необходимость
Из свойства 4. по модулю  при , , следует:

 ,

а по свойству 2.

 ,

поэтому

 

и

 

, поэтому если  — простое, то  и из последних двух свойств  делит

 

Далее, из свойств 1. и 2.

 ,

но по свойству 3.

 ,

то есть  делит , а значит и .

Достаточность
Если  делит , то из доказательства необходимости следует, что оно делит и .  взаимно просто с  по свойству 1., а по свойству 2. — делит . Но тогда каждый простой делитель числа  представим в виде , то есть  — простое.

История 
Критерий простоты был предложен французским математиком Люка в 1878 году. В частности, Люка показал, что алгоритм позволяет проверять простоту  для простых . В 1930 году американский математик Лемер полностью доказал справедливость критерия для всех простых нечётных  в своей диссертации на соискание учёной степени доктора философии.

В 1952 году Робинсон при поддержке Лемера провел вычисления на компьютере SWAC с использованием теста Люка — Лемера, результатом которого стало открытие простых чисел  и . Позднее в этом же году были открыты ,  и .

Лёгкость реализации теста и рост вычислительных мощностей компьютеров позволили фактически любому человеку заниматься поиском простых чисел Мерсенна. Так, в 1978 году два американских старшеклассника Лора Никель и Курт Нолл (Лемер преподавал им теорию чисел) за 3 года работы доказали простоту числа , используя суперкомпьютер CDC Cyber 176 в Калифорнийском университете.

Наибольшее из известных простых чисел Мерсенна на 2018 год, полученное с помощью теста Люка — Лемера, это .

Примеры 
Требование нечётности  в условии критерия существенно, так как  — простое, но .

Число  — простое. Действительно,
 
 
 
 
 
 
 
 
 
 
 
 

Применение теста к числу  показывает, что оно составное:

 
 
 
 
 
 
 
 
 
 

Действительно, .

Вычислительная сложность 
В рассматриваемом тесте две основные операции: возведение в квадрат и деление по модулю. Эффективный алгоритм деления по модулю числа Мерсенна на компьютере (фактически сводящийся к нескольким операциям битового сдвига) дает следующая теорема:

Например, чтобы вычислить остаток от деления числа  на , нужно исходное число преобразовать в двоичный вид: , и, согласно теореме, разбивать  на две части каждый раз, когда оно превосходит :

 

При использовании этого способа деления по модулю вычислительная сложность теста будет определяться сложностью алгоритма возведения в квадрат. Длина  составляет  бит, а алгоритм умножения двух чисел, например, «в столбик», имеет сложность . Так как возведение в квадрат в тесте происходит  раз, то вычислительная сложность алгоритма равна . Тест можно ускорить, если использовать алгоритмы быстрого умножения больших целых чисел, например, метод умножения Шёнхаге — Штрассена. Сложность теста в таком случае составит .

Вариации и обобщения 
Условие в тесте можно ослабить и потребовать лишь, чтобы , откуда немедленно следует:

 .

В 1930 году Лемер вывел критерий простоты для чисел вида , где , а в 1969 году  модифицировал тест Люка — Лемера для чисел такого вида, который впоследствии был дополнен Стечкиным. Возможно обобщение теста и на числа вида .

 были доказаны критерии простоты, аналогичные тесту Люка — Лемера, для чисел вида  и , а также для некоторых чисел вида , где  — простое .

Существует более общий -тест простоты, который применим для любого натурального числа , если известно полное или частичное разложение на простые множители числа  или .

Применения 
Благодаря тесту Люка — Лемера, простые числа Мерсенна удерживают лидерство как самые большие известные простые числа, хотя и до существования теста числа Мерсенна почти всегда были наибольшими простыми. Так, в 1588 году была доказана простота чисел  и .

Евклид доказал, что всякое число вида  — совершенное, если  — простое, а Эйлер показал, что все чётные совершенные числа имеют такой вид; поэтому тест Люка — Лемера фактически позволяет найти все чётные совершенные числа.

Именно этот тест лежит в основе проекта распределённых вычислений GIMPS, занимающегося поиском новых простых чисел Мерсенна, хотя до сих пор не доказано, что их бесконечно много.

Также данный тест используется для тестирования аппаратного обеспечения. Так, в 1992 году специалисты компании  протестировали новый суперкомпьютер компании Cray, используя программу, написанную  для поиска простых чисел Мерсенна. В результате за 19 часов работы программы было открыто простое число .

Примечания 

Тесты простоты