- Тест Люка
-
Тест Люка — Лемера — эффективный тест простоты для чисел Мерсенна. Благодаря этому тесту самые большие простые числа всегда были числами Мерсенна даже задолго до появления компьютеров.[1]
Содержание
История
Тест был предложен французским математиком Люка в 1878 году и дополнен американским математиком Лемером в 1930 году. Полученный тест носит имя двух ученых, которые совместно открыли его, даже не встречаясь при жизни. В 1952 году Робинсон при поддержке Лемера провел вычисления на компьютере SWAC с использованием теста Люка - Лемера, результатом которого стало открытие простых чисел
,
. Позднее, в этом же году были открыты
,
,
.[2]
Тест
Тест Люка — Лемера базируется на том наблюдении, что простота числа Мерсенна
влечёт простоту числа
, и следующем утверждении:
Пусть
- простое число, причем
. Определим последовательность
следующим образом:
Тогда
- простое тогда и только тогда, когда
Для установления простотыпоследовательность чисел
вычисляется по модулю числа
(т. е. вычисляются не сами числа
, длина которых растёт экспоненциально; а остатки от деления
на
, длина которых ограничена p битами). Последнее число в этой последовательности
называется вычетом Люка — Лемера. Таким образом, число Мерсенна
является простым тогда и только тогда, когда число
простое, и вычет Люка — Лемера равен нулю.
Возможными значениями
являются: 4, 10, 52, 724, 970, 10084, … (последовательность A018844 в OEIS)
Сложность
Сложность теста для числа
равна
[3] , так как в процессе выполнения теста мы производим
возведений в квадрат и вычитаний по модулю
. Длина
-
бит, причем самый простой алгоритм умножения чисел имеет сложность
. Для ускорения теста следует использовать алгоритмы быстрого умножения больших целых чисел, например, метод умножения Шёнхаге — Штрассена. Сложность в таком случае составит
.
Примеры
Рассмотрим выполнение теста для числа Мерсенна
.
Следовательно, число
- простое.
Доказательство
Теорема: Пусть
- простое число, причем
. Определим последовательность
следующим образом:
Тогда- простое тогда и только тогда, когда
.
Доказательство теоремы основано на простейших принципах теории чисел. Исследуем некоторые свойства рекуррентных последовательностей. Положим, чтоСледующие свойства доказываются по индукции:
Лемма: Пусть
- простое и
, тогда справедливо следующее утверждение. Если
, то
.
Доказательство леммы: Положим,
. Используем выше описанные свойства, чтобы получить значения для
и
:
, в то время как
.
Таким же способом получим:
и
. Иначе говоря,
и
, откуда следует утверждение леммы, если взять
.
Далее, раскроем выражение последовательностей по биному Ньютона:
,
Теперь, если мы положим
, где
- простое число, большее 2, и учтем, что
кратно
за исключением тех случаев, когда
и
, мы получим:
,
.
Если
теорема Ферма утверждает, что
. Поэтому
, то есть
. Если
, то
, то есть
. Таким же способом получим, что
, если
. Мы доказали, что для любого простого числа, существует целое число
такое, что
.
Лемма: Если- положительное целое число, и
- наименьшее число такое, что
, то мы имеем:
тогда и только тогда, когда
кратно
.
Доказательство: Заметим, что последовательность
совпадает с последовательностью
по
, где
- взаимно простое с
, так как :
.
Доказательство теоремы: по индукции:.
Более того, из
следует, что
. Отсюда следует, что
и
не имеют общих нечетных делителей. Если
, то для
и
можем записать
Теперь, если
, то
должно быть делителем числа
, но не должно делить
, поэтому
. Докажем, что
. Пусть
. Числа
больше 3, так как
нечетное и выполняется
,
- простое по условию. Используя ранее доказанные леммы, получим
, где
где
. Отсюда следует, что
кратно
. Положим
;
. Так как
- четное,
. Используем ранее доказанные факты и получим
; следовательно
и
либо
. Заметим, что
- степень двойки. Отсюда следует, что
и
. Если
- составное, то должно быть
, где
и
- простые числа. Дальнейшее разложение на простые числа, если
- нечетное, невозможно, поэтому
- простое.
- Наоборот, предположим, что
- простое. Покажем, что
. Для этого достаточно показать, что
, так как
.
Так как
- простое, то биномиальный коэффициент
делится на
кроме тех случаев, когда
или
; следовательно
.
Здесь
, поэтому
по теореме Ферма. Наконец, используя простейший случай квадратичного закона взаимности, покажем, что
, так как
и
. Это означает, что
, так что
. [4]
Псевдокод
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). Возможно обобщение теста для чисел вида
.[5] Также существует более общий вариант - тест Люка, который применим для любого натурального числа
, если известно разложение на простые множители числа
.
Применения
Благодаря тесту Люка — Лемера простые числа Мерсенна удерживают лидерство как самые большие известные простые числа. Именно тест Люка — Лемера лежит в основе проекта распределённых вычислений GIMPS, занимающимся поиском новых простых чисел Мерсенна.
См.Также
Примечания
- ↑ Paulo Ribenboim The Little Book of Bigger Primes. — Springer. — 2004. — С. 78. — ISBN 978-0387201696
- ↑ Paulo Ribenboim The Little Book of Bigger Primes. — Springer. — 2004. — С. 79. — ISBN 978-0387201696
- ↑ Eric Bach; Jeffrey Shallit Algorithmic Number Theory, Vol. 1: Efficient Algorithms. — The MIT Press, 1996. — С. 275. — ISBN 978-0262024051
- ↑ Donald E. Knuth The Art of Computer Programming, Volume 2: Seminumerical Algorithms. — 3 (3 edition). — Addison-Wesley Professional, 1997. — С. 2. — 392 с. — ISBN 978-0201896848
- ↑ H. C. Williams A class of primality tests for trinomials which includes the Lucas-Lehmer test. (англ.). Архивировано из первоисточника 23 декабря 2012. Проверено 28 ноября 2012.
Литература
- Weisstein, Eric W. Lucas-Lehmer Test (англ.) на сайте Wolfram MathWorld.
- А.Н.Рудаков Числа Фибоначчи и простота числа 2127-1 // Математическое Просвещение. — 2000. — В. 4 (третья серия).
- Donald E. Knuth The Art of Computer Programming, Volume 2: Seminumerical Algorithms. — Addison-Wesley Professional. — 1997. — С. 389-394. — ISBN 978-0201896848
- Paulo Ribenboim The Little Book of Bigger Primes. — Springer. — 2004. — С. 75-80. — ISBN 978-0387201696
- Eric Bach; Jeffrey Shallit Algorithmic Number Theory, Vol. 1: Efficient Algorithms. — The MIT Press, 1996. — С. 273-275. — ISBN 978-0262024051
Категория:- Тесты простоты
Wikimedia Foundation. 2010.