Открыть главное меню

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

(перенаправлено с «Тест Люка-Лемера»)

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

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

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

ФормулировкаПравить

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

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

  [2],

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


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

LLT(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].

Наибольшее из известных простых чисел Мерсенна на 2018 год, полученное с помощью теста Люка — Лемера, это  [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. BulletinIrish 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. Robinson R. M. Mersenne and Fermat Numbers // Proc. Amer. Math. Soc. / K. OnoAMS, 1954. — Vol. 5, Iss. 5. — P. 842. — ISSN 0002-9939; 1088-6826doi:10.2307/2031878
  6. 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
  7. последовательность A018844 в OEIS
  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: 282,589,933-1 (англ.). GIMPS (21 December 2018). Дата обращения 28 февраля 2019.
  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 MathematicsMathematical 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 — 5 — Addison-Wesley, 2004. — P. 261–265. — 744 p. — ISBN 978-0-321-23707-1
  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-165arXiv:1112.2412
  20. Clawson C. C. Mathematical Mysteries: The Beauty and Magic of NumbersSpringer US, 1996. — P. 174. — 314 p. — ISBN 978-0-306-45404-2doi:10.1007/978-1-4899-6080-1