Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 48 стр.

                                                                          49

Мерсенна давно удерживают лидерство как самые большие известные
простые числа. Этот тест был придуман Люка (Lucas) в 1878 г. и в 1930 г.
усовершенствован Лемером (Lehmer).
      Тест Люка — Лемера базируется на том, что простота числа Мерсенна
Mp влечёт простоту числа p, и следующем утверждении:

      Тест Люка. Для простого числа p ≥ 3 число Mp является простым
тогда и только тогда, когда оно делит число Lp − 1, где числа Lk
определяются рекуррентным соотношением:

                           L1 = 4, Lk+1 = L2k − 2

      Для     установления     простоты     Mp      достаточно    вычислять
последовательность чисел по модулю числа Mp , длина которого ограничена
p битами. Последнее число в этой последовательности Lp − 1(modMp )
называется вычетом Люка — Лемера. Таким образом, число Мерсенна Mp
является простым тогда и только тогда, когда число p простое и вычет
Люка — Лемера равен нулю.
      Еще в 1876 г. Люка с помощью этого критерия установил, что число

            2127 − 1 = 170141183460469231731687303715884105727

является простым. Это число оставалось самым большим известным простым
числом до 1951 г., т.е. на протяжении 75 лет.
      К сентябрю 2004 г. было найдено 44 простых числа Мерсенна, 4
сентября 2006 г. было аннонсировано 45-е число 232 582 657 −1. На сегодняшний
день известно 47 простых чисел Мерсенна. Самым большим известным
простым числом является число Мерсенна Mp = 243112609 − 1, найденное
в августе 2008 г. в рамках проекта распределённых вычислений GIMPS.
Длина его составляет 12978189 десятичных цифр, что позволило GIMPS в
2009 г. получить премию в 100000 долларов США, назначенную сообществом
Electronic Frontier Foundation за нахождение простого числа, длина которого
превышает 10 миллионов десятичных цифр.