Эта статья входит в число хороших статей

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

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

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

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

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

Формулировка[править | править вики-текст]

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

Пусть простое нечётное. Число Мерсенна простое тогда и только тогда, когда оно делит нацело -й член последовательности

[2],

задаваемой рекуррентно:


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

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

Возможными значениями являются: [5][6][7].

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

Если числа и — простые, то .

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

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

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

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

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

1.
2.
3.
4. Если , , и
,
то
5. Если — простое, такое, что взаимно просто с , то делит нацело ,
где , а символ Лежандра.

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

Необходимость[править | править вики-текст]

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

,

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

,

поэтому

и

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

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

,

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

,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для целого числа и числа Мерсенна имеет место сравнение по модулю

,

причём умножение на по модулю равносильно левому циклическому сдвигу на бит (если , то сдвиг осуществляется в обратную сторону).

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

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

Вариации и обобщения[править | править вики-текст]

Условие в тесте можно ослабить[8] и потребовать лишь, чтобы , откуда немедленно следует:

.

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

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

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

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

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

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

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

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

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

  1. 1 2 Jaroma J. H. Note on the Lucas–Lehmer Test // Irish Math. Soc. Bulletin Irish Mathematical Society, 2004. — Vol. 54. — P. 63–72. — ISSN 0791-5578
  2. последовательность A003010 в OEIS
  3. Abhijit Das. Computational Number Theory. — 2-е изд. — CRC Press, 2016. — P. 290—292. — 614 p. — (Discrete Mathematics and Its Applications). — ISBN 1482205823.
  4. 1 2 3 4 Крэндалл Р., Померанс К. Простые числа. Криптографические и вычислительные аспекты = Prime Numbers: A Computational Perspective / пер. с англ. А. В. Бегунца, Я. В. Вегнера, В. В. Кнотько, С. Н. Преображенского, И. С. Сергеева. — М.: УРСС, Книжный дом «Либроком», 2011. — С. 198—216, 498—500, 510—513. — 664 с. — ISBN 978-5-453-00016-6, 978-5-397-02060-2.
  5. последовательность A018844 в OEIS
  6. Robinson R. M. Mersenne and Fermat Numbers // Proc. Amer. Math. Soc. / K. OnoAMS, 1954. — Vol. 5, Iss. 5. — P. 842–846. — ISSN 0002-9939; 1088-6826doi:10.2307/2031878
  7. Kravitz S. The Lucas–Lehmer Test for Mersenne Numbers // Fibonacci Quarterly / C. CooperThe Fibonacci Association, 1970. — Vol. 8, Iss. 1. — P. 1–3. — ISSN 0015-0517
  8. 1 2 Трост Э. Простые числа = Primzahlen / под ред. А. О. Гельфонда, пер. с нем. Н. И. Фельдмана. — М.: Физматлит, 1959. — С. 42—46. — 137 с. — 15 000 экз.
  9. 1 2 3 4 5 Уильямс Х. Проверка чисел на простоту с помощью вычислительных машин = Primality testing on a computer // Лупанов О. Б. Кибернетический сборник : журнал / пер. с англ. С. В. Чудова. — М.: Мир, 1986. — Вып. 23. — С. 51—99. — ISBN N/A, ББК 32.81, УДК 519.95.
  10. Ribenboim P. The Little Book of Bigger Primes — 2nd edition — Springer-Verlag New York, 2004. — P. 75–87. — 356 p. — ISBN 978-0-387-21820-5
  11. Devlin K. Mathematics: The New Golden Age — 2nd edition — UK: Penguin Books, 1998. — P. 75–87. — 320 p. — ISBN 978-0-14-193605-5
  12. GIMPS Project Discovers Largest Known Prime Number: 274,207,281-1 (англ.). GIMPS (January 2016). Проверено 1 декабря 2016.
  13. 1 2 Koshy T. Elementary Number Theory with Applications. — 2nd edition. — Academic Press, 2007. — P. 369—381. — 800 p. — ISBN 9780080547091.
  14. Bach E., Shallit J. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. — The MIT Press, 1996. — P. 41—66. — 496 p. — (Foundations of Computing). — ISBN 978-0262024051.
  15. Williams H. C. A Class of Primality Tests for Trinomials Which Includes the Lucas-Lehmer Test // Pacific Journal of Mathematics Mathematical Sciences Publishers, 1982. — Vol. 98, Iss. 2. — P. 477–494. — ISSN 0030-8730doi:10.2140/PJM.1982.98.477
  16. Rosen K. H. Elementary Number Theory and Its Applications — 5th edition — Addison-Wesley, 2004. — P. 261–265. — 744 p. — ISBN 978-0321237071
  17. Хассе Г. Лекции по теории чисел = Vorlesungen über die Theorie der algebraischen Zahlen / под ред. И. Р. Шафаревича, пер. с нем. В. Б. Демьянова. — М.: Издательство иностранной литературы, 1953. — С. 36—44. — 528 с.
  18. Mathematics and Research Strategy (англ.). GIMPS. Проверено 4 декабря 2016.
  19. Wolf M. Computer Experiments with Mersenne Primes // Computational Methods in Science and Technology — 2013. — Vol. 19, Iss. 3. — P. 157–165. — ISSN 1505-0602doi:10.12921/CMST.2013.19.03.157-165
  20. Clawson C. C. Mathematical Mysteries: The Beauty and Magic of Numbers Springer US, 1996. — P. 174. — 314 p. — ISBN 978-0-306-45404-2doi:10.1007/978-1-4899-6080-1