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

Тест Люка́ — Ле́мера — эффективный тест простоты для чисел Мерсенна. Этот тест был предложен Э. Люка (Lucas) в 1878-ом году и в 1930-ом году усовершенствован Д. Лемером (Lehmer).

Тест Люка—Лемера базируется на том наблюдении, что простота числа Мерсенна Mp = 2p - 1 влечёт простоту числа p, и следующем утверждении:

Для простого числа p число Mp является простым тогда и только тогда, когда оно делит число Lp - 1, где числа Lk определяются рекуррентным соотношением: L_1 = 4, L_{k+1} = L_k^2 - 2.

Для установления простоты Mp последовательность чисел L_1, L_2, \ldots, L_{p-1} достаточно вычислять по модулю числа Mp (т. е. вычислять не сами числа Lk, длина которых растёт экспоненциально; а остатки от деления Lk на Mp, длина которых ограничена p битами). Последнее число в этой последовательности Lp - 1mod Mp называется вычетом Люка — Лемера. Таким образом, число Мерсенна Mp является простым тогда и только тогда, когда число p — простое и вычет Люка — Лемера равен нулю.

Возможными значениями L1 являются: 4, 10, 52, 724, 970, ... (Последовательность A018844 из Энциклопедии целочисленных последовательностей)

Благодаря тесту Люка — Лемера простые числа Мерсенна удерживают лидерство как самые большие известные простые числа. Именно тест Люка — Лемера лежит в основе проекта распределённых вычислений GIMPS, занимающимся поиском новых простых чисел Мерсенна.

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home