Эта статья является кандидатом в добротные статьи

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

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

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

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

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

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

(последовательность A003010 в OEIS),

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


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

Возможными значениями являются: (последовательность A018844 в OEIS)[6].

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

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

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

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

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

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

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

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

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

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

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

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

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

Покажем, что число составное. Действительно:

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

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

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

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

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

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

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

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

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

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

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

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


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


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

  1. 1 2 С. Коутинхо. Введение в теорию чисел. Алгоритм RSA = The Mathematics of Ciphers: Number Theory and RSA Cryptography / под ред. С. К. Ландо, пер. с англ. С. А. Кулешова. — М.: Постмаркет, 2001. — 328 с. — ISBN 590109509Х.
  2. 1 2 Paulo Ribenboim. The Little Book of Bigger Primes. — 2nd edition. — Springer, 2004. — 356 p. — ISBN 0387201696.
  3. 1 2 3 Х. Уильямс Проверка чисел на простоту с помощью вычислительных машин = Primality testing on a computer // О. Б. Лупанов Кибернетический сборник : журнал / пер. с англ. С.В. Чудова. — М.: Мир, 1986. — Вып. 23. — ISBN N/A, ББК 32.81, УДК 519.95.
  4. 1 2 Кнут, Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы = The Art of Computer Programming. Volume 2. Seminumerical Algorithms / под ред. Ю. В. Козаченко. — 3. — Москва: Вильямс, 2001. — Т. 2. — 832 с. — ISBN 5-8459-0081-6.
  5. Abhijit Das. Computational Number Theory. — 2-е изд. — CRC Press, 2016. — 614 p. — (Discrete Mathematics and Its Applications). — ISBN 1482205823.
  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. Трост Э. Простые числа = Primzahlen / под ред. А. О. Гельфонда, пер. с нем. Н. И. Фельдмана. — М.: Физматлит, 1959. — 137 с. — 15 000 экз.
  8. 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
  9. Devlin K. Mathematics: The New Golden Age — 2nd edition — UK: Penguin Books, 1998. — 320 p. — ISBN 978-0-14-193605-5
  10. GIMPS Project Discovers Largest Known Prime Number: 274,207,281-1 (англ.). GIMPS (January 2016). Проверено 1 декабря 2016.
  11. Eric Bach; Jeffrey Shallit. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. — The MIT Press, 1996. — 496 p. — (Foundations of Computing). — ISBN 978-0262024051.
  12. H. C. Williams. A class of primality tests for trinomials which includes the Lucas-Lehmer test. (англ.). Проверено 28 ноября 2012. Архивировано из первоисточника 23 декабря 2012.
  13. Г. Хассе. Лекции по теории чисел = Vorlesungen über die Theorie der algebraischen Zahlen / под ред. И. Р. Шафаревича, пер. с нем. В. Б. Демьянова. — М.: Издательство иностранной литературы, 1953. — 528 с.
  14. Mathematics and Research Strategy (англ.). GIMPS. Проверено 4 декабря 2016.
  15. Marek Wolf Computer experiments with Mersenne primes (англ.) // Computational Methods in Science and Technology. — 2013. — Vol. 19, no. 3. — P. 157-165. — DOI:10.12921/cmst.2013.19.03.157-165. — arXiv:1112.2412v1.
  16. Calvin C. Clawson. Mathematical Mysteries: The Beauty and Magic of Numbers. — Springer, 2013. — 314 p. — ISBN 1489960805.