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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Тест Люка — Лемера — ефективний тест простоти для чисел Мерсенна. Завдяки цьому тесту найбільшими відомими простими числами завжди були прості числа Мерсенна, причому навіть до появи комп'ютерів[1].


Історія

[ред. | ред. код]

Тест був запропонований французьким математиком Люка 1878 року і доповнений американським математиком Лемером[en] 1930 року. Отриманий тест носить ім'я двох вчених, які спільно відкрили його, навіть не зустрічаючись за життя. 1952 року Робінсон за підтримки Лемера провів обчислення на комп'ютері SWAC з використанням тесту Люка — Лемера, результатом якого стало відкриття простих чисел і . Пізніше того ж року були відкриті , і [1].

Тест Люка — Лемера базується на тому спостереженні, що простота числа Мерсенна тягне простоту числа , і в наступному твердженні:

Нехай  — просте число, причому . визначимо послідовність таким чином:

Тоді  — просте тоді і тільки тоді, коли .

Для встановлення простоти послідовність чисел обчислюється по модулю числа (тобто обчислюються не власне числа , довжина яких росте експоненціально, а остачі від ділення на , довжина яких обмежена p бітами). Останнє число в цій послідовності називається вирахуванням Люка — Лемера. Таким чином, число Мерсенна є простим тоді і тільки тоді, коли число просте, і вирахування Люка — Лемера дорівнює нулю.

Можливими значеннями є: 4, 10, 52, 724, 970, 10084, …

Обчислювальна складність

[ред. | ред. код]

Обчислювальна складність тесту для числа дорівнює [2], оскільки в процесі тесту виконується піднесення до квадрату та вирахувань по модулю . Довжина становить біт, причому найпростіший алгоритм множення чисел має складність . Для прискорення тесту слід використовувати алгоритми швидкого множення великих цілих чисел, наприклад, алгоритм Шьонхаге — Штрассена. Складність тесту в такому випадку становитиме .

Приклади

[ред. | ред. код]

Розглянемо виконання тесту для числа Мерсенна .

Отже, число  — просте.

Доведення

[ред. | ред. код]

Теорема: Нехай  — просте число, причому . Визначимо послідовність таким чином:

Тоді  — просте тоді і тільки тоді, коли .

Доведення теореми засновано на властивостях послідовностей Люка і :

Такі властивості доводяться по індукції:

Лема: Нехай  — просте і , тоді справедливе наступне твердження. Якщо , то .

Доказ леми: Покладемо , . Використовуємо вище описані властивості, щоб отримати значення для і :

, в той час як .

Тим же способом отримаємо:

і

Інакше кажучи,

і ,

звідки випливає твердження леми, якщо взяти .

Далі, розкривається вираз послідовностей за формулою біному Ньютона:

Тепер, якщо ми покладемо , де  — просте число, більше 2, і врахуємо, що кратне за винятком тих випадків, коли і , ми отримаємо:

, .

Якщо теорема Ферма стверджує, що . Тому , тобто . Якщо , то

тобто . У той же спосіб отримується результат, що , якщо . Отже доведено, що для будь-якого простого числа, існує ціле число таке, що .

Лема: Якщо  — додатне ціле число, і  — найменше число таке, що , то ми маємо:

тоді і тільки тоді, коли кратне .

Доведення: Зауважимо, що послідовність збігається з послідовністю по модулю , де число взаємно просте з , так як: .

Доведення теореми: По індукції маємо

.

Більш того, з слідує, що . Звідси слід, що і не мають загальних непарних дільників. Якщо , то для і можна записати:

Тепер, якщо , то повинно бути дільником числа , але не повинно ділити , тому . Доведемо, що . Нехай . Числа більше 3, так як непарне і виконується ,  — просте за умовою. Використовуючи раніше доведені леми, отримаємо , де

де . Звідси випливає, що кратне . Покладемо ; . Так як  — парне, . Використовуємо раніше доведені факти і отримаємо ; отже і або . Зауважимо, що  — ступінь двійки. Звідси випливає, що і . Якщо  — складене, то має бути , де і  — прості числа. Подальше розкладання на прості числа, якщо  — непарне, неможливо, тому  — просте.

Навпаки, припустимо, що  — просте. Покажемо, що . Для цього достатньо показати, що , так як .

Так як  — просте, то біноміальний коефіцієнт ділиться на крім тих випадків, коли чи . Отже:

.

Тут , тому за малої теореми Ферма. Нарешті, використовуючи найпростіший випадок квадратичного закону взаємності, покажемо, що , так як і . Це значить, що , так що . [3]

Псевдокод

[ред. | ред. код]
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

Модифікації

[ред. | ред. код]

Для чисел виду , де існує модифікація цього тесту[en], розроблена Хансом Різелем[en]. Можливо узагальнення тесту для чисел виду [4]. Також існує більш загальний варіант — тест Люка, який застосовний для будь-якого натурального числа , якщо відоме розкладання на прості множники числа .

Застосування

[ред. | ред. код]

Завдяки тесту Люка — Лемера прості числа Мерсенна утримують лідерство як найбільші відомі прості числа[5]. Саме тест Люка — Лемера лежить в основі проекту розподілених обчислень GIMPS, що шукає нові прості числа Мерсенна.

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. а б Paulo Ribenboim. The Little Book of Bigger Primes. — Springer. — 2004. — С. 78. — (2-ге видання) — ISBN 978-0387201696.
  2. Eric Bach; Jeffrey Shallit. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. — The MIT Press, 1996. — С. 275. — ISBN 978-0262024051.
  3. Donald E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. — Addison-Wesley Professional, 1997. — С. 2. — (2-ге видання) — ISBN 978-0201896848.
  4. H. C. Williams. A class of primality tests for trinomials which includes the Lucas-Lehmer test (англ.). Архів оригіналу за 23 грудня 2012. Процитовано 28 листопада 2012.
  5. The «Top Ten» Record Primes(англ.).

Література

[ред. | ред. код]