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

Тест Люка — Лемера — это детерминированный алгоритм проверки простоты чисел Мерсенна, то есть чисел вида \( M_p = 2^p - 1 \), где \( p \) — простое число. Тест позволяет за полиномиальное время (относительно длины записи числа) определить, является ли число Мерсенна простым, и является одним из наиболее эффективных известных методов для поиска больших простых чисел. Назван в честь французского математика Эдуарда Люка, разработавшего основу метода в 1876 году, и американского математика Деррика Лемера, усовершенствовавшего его в 1930 году.

История

Предпосылки

Интерес к числам Мерсенна возник ещё в античности: Евклид доказал, что если \( 2^p - 1 \) простое, то число \( 2^{p-1}(2^p - 1) \) является совершенным. Однако проверка простоты таких чисел вручную была крайне трудоёмкой. К середине XIX века было известно лишь несколько простых чисел Мерсенна: для \( p = 2, 3, 5, 7, 13, 17, 19, 31 \). Последнее из них (для \( p = 31 \)) было найдено Леонардом Эйлером в 1772 году.

Работа Эдуарда Люка

В 1876 году французский математик Эдуард Люка опубликовал работу, в которой предложил критерий простоты для чисел Мерсенна, основанный на последовательности остатков. Он показал, что число \( M_p \) простое тогда и только тогда, когда \( p \)-й член определённой рекуррентной последовательности делится на \( M_p \). Люка лично проверил числа вплоть до \( p = 127 \), но его вычисления содержали ошибки — он ошибочно посчитал \( M_{67} \) простым (на самом деле оно составное). Тем не менее, его метод стал первым эффективным алгоритмом для этой задачи.

Усовершенствование Деррика Лемера

В 1930 году американский математик Деррик Лемер, будучи аспирантом, существенно упростил и формализовал критерий Люка. Он предложил использовать последовательность вида \( s_{n+1} = s_n^2 - 2 \), начинающуюся с \( s_0 = 4 \), и доказал, что \( M_p \) простое тогда и только тогда, когда \( s_{p-2} \equiv 0 \pmod{M_p} \). Этот вариант стал известен как тест Люка — Лемера. Лемер также исправил ошибки Люка и подтвердил простоту \( M_{127} \), который оставался самым большим известным простым числом до 1952 года.

Компьютерная эра

С появлением электронных вычислительных машин в середине XX века тест Люка — Лемера стал основой для поиска новых простых чисел Мерсенна. В 1952 году Рафаэль Робинсон с помощью компьютера SWAC (Standards Western Automatic Computer) нашёл пять новых простых чисел Мерсенна: \( M_{521}, M_{607}, M_{1279}, M_{2203}, M_{2281} \). С тех пор все рекордные простые числа (за исключением нескольких случаев) были найдены именно с помощью этого теста. В 1996 году был запущен проект распределённых вычислений GIMPS (Great Internet Mersenne Prime Search), который использует тест Люка — Лемера для поиска простых чисел Мерсенна на компьютерах добровольцев по всему миру. По состоянию на 2025 год, с помощью GIMPS найдено 18 из 52 известных простых чисел Мерсенна, включая самое большое — \( M_{136279841} \) (открыто в октябре 2024 года).

Алгоритм

Формальное описание

Тест Люка — Лемера применяется только к числам Мерсенна \( M_p = 2^p - 1 \), где \( p \) — нечётное простое число (случай \( p = 2 \) тривиален: \( M_2 = 3 \) — простое). Алгоритм состоит из следующих шагов:

1. Задать начальное значение \( s_0 = 4 \).
2. Для \( i \) от 1 до \( p-2 \) вычислить \( s_i = (s_{i-1}^2 - 2) \bmod M_p \).
3. Если \( s_{p-2} \equiv 0 \pmod{M_p} \), то \( M_p \) — простое. Иначе — составное.

Пример

Рассмотрим \( p = 5 \), \( M_5 = 31 \).

• \( s_0 = 4 \)
• \( s_1 = (4^2 - 2) \bmod 31 = 14 \)
• \( s_2 = (14^2 - 2) \bmod 31 = 194 \bmod 31 = 8 \)
• \( s_3 = (8^2 - 2) \bmod 31 = 62 \bmod 31 = 0 \)

Так как \( s_3 = 0 \), число \( M_5 = 31 \) является простым.

Свойства

• Начальное значение: Хотя классический тест использует \( s_0 = 4 \), существуют и другие допустимые начальные значения, например \( s_0 = 10 \), \( s_0 = 2/3 \) (в поле вычетов) или \( s_0 = 2^p - 2 \). Однако \( s_0 = 4 \) является наиболее распространённым.
• Модульная арифметика: Все вычисления проводятся по модулю \( M_p \), что позволяет работать с числами, не превосходящими \( M_p \), и избегать неограниченного роста значений.
• Сложность: Алгоритм требует \( O(p) \) итераций, каждая из которых включает возведение в квадрат и вычитание 2. При использовании быстрого умножения (например, алгоритма Шёнхаге — Штрассена) сложность составляет \( O(p^2 \log p \log \log p) \) битовых операций. Для современных рекордных чисел (с \( p \) порядка 100 миллионов) это требует нескольких дней вычислений на мощном компьютере.

Доказательство

Необходимость

Если \( M_p \) простое, то \( s_{p-2} \equiv 0 \pmod{M_p} \). Доказательство основано на свойствах последовательности Люка и квадратичных вычетов. В частности, можно показать, что \( s_{p-2} = \omega^{2^{p-2}} + \omega^{-2^{p-2}} \), где \( \omega = 2 + \sqrt{3} \), и используя малую теорему Ферма, получить, что \( \omega^{M_p} \equiv \omega \pmod{M_p} \), откуда следует \( s_{p-2} \equiv 0 \).

Достаточность

Если \( s_{p-2} \equiv 0 \pmod{M_p} \), то \( M_p \) простое. Доказательство использует противоречие: если \( M_p \) составное, то существует простой делитель \( q < \sqrt{M_p} \), и можно показать, что порядок \( \omega \) в мультипликативной группе поля \( \mathbb{F}_{q^2} \) равен \( 2^p \), что невозможно, так как \( 2^p > q^2 - 1 \). Полное доказательство впервые было опубликовано Лемером в 1930 году.

Применение

Поиск больших простых чисел

Тест Люка — Лемера является основным инструментом для поиска рекордных простых чисел. Все 10 самых больших известных простых чисел (по состоянию на 2025 год) являются числами Мерсенна и были найдены с помощью этого теста. Например, самое большое простое число, известное на 2025 год, \( M_{136279841} \), было открыто в рамках проекта GIMPS. Тест позволяет проверить число с миллионами десятичных знаков за разумное время.

Криптография

Хотя числа Мерсенна редко используются непосредственно в криптографии (из-за их специфической формы), тест Люка — Лемера применяется в некоторых криптосистемах, основанных на сложности факторизации или дискретного логарифмирования, где требуется генерация больших простых чисел. Например, в протоколах Диффи — Хеллмана или RSA иногда используются простые числа Мерсенна для оптимизации вычислений.

Распределённые вычисления

Проект GIMPS, использующий тест Люка — Лемера, является одним из крупнейших проектов распределённых вычислений в мире. На 2025 год в нём участвуют более 100 000 добровольцев, предоставляющих вычислительные мощности своих компьютеров. Проект также использует модифицированную версию теста — тест Люка — Лемера — Риселя (LLR) — для проверки простоты чисел вида \( k \cdot 2^n - 1 \).

Ограничения и альтернативы

Ограничения

• Тест применим только к числам Мерсенна. Для произвольных чисел существуют другие методы (например, тест Миллера — Рабина), но они являются вероятностными.
• Алгоритм требует хранения и обработки чисел размером до \( M_p \), что для рекордных значений (сотни миллионов бит) предъявляет высокие требования к памяти и вычислительной мощности.
• Тест не даёт информации о делителях, если число оказалось составным — он лишь сообщает факт составности.

Альтернативы

• Тест Пепина: используется для проверки простоты чисел Ферма (\( F_n = 2^{2^n} + 1 \)).
• Тест Миллера — Рабина: вероятностный тест для произвольных чисел, но не гарантирует простоту.
• Тест AKS: детерминированный тест для произвольных чисел, работающий за полиномиальное время, но на практике менее эффективен для больших чисел Мерсенна.

Интересные факты

• Тест Люка — Лемера был использован для проверки простоты числа \( M_{127} \), которое оставалось самым большим известным простым числом в течение 75 лет (с 1876 по 1951 год).
• В 1952 году с помощью теста было найдено сразу пять новых простых чисел Мерсенна, что стало возможным благодаря появлению первых компьютеров.
• Проект GIMPS выплачивает денежные призы за открытие новых простых чисел Мерсенна: 50 000 долларов США за первое простое число с более чем 10 миллионами десятичных знаков (найдено в 2008 году) и 150 000 долларов за число с более чем 100 миллионами знаков (найдено в 2024 году).
• Алгоритм теста Люка — Лемера реализован в специализированном программном обеспечении, таком как Prime95 и MPrime, которые оптимизированы для архитектуры x86-64 и используют SIMD-инструкции (AVX, AVX-512) для ускорения вычислений.

Источники

• Lehmer, D. H. (1930). "An Extended Theory of Lucas' Functions". Annals of Mathematics.
• Lucas, É. (1878). "Théorie des fonctions numériques simplement périodiques". American Journal of Mathematics.
• Crandall, R., & Pomerance, C. (2005). "Prime Numbers: A Computational Perspective". Springer.
• GIMPS (Great Internet Mersenne Prime Search). Официальный сайт проекта.
• Weisstein, E. W. "Lucas-Lehmer Test". MathWorld — A Wolfram Web Resource.