Тест на простоту Лукаса-Лемера - Lucas–Lehmer primality test

В математика, то Тест Лукаса-Лемера (LLT) это тест на простоту за Числа Мерсенна. Первоначально тест был разработан Эдуард Лукас в 1856 г.^{[нужна цитата ]} и впоследствии улучшенный Лукасом в 1878 году и Деррик Генри Лемер в 1930-е гг.

Тест

Тест Лукаса – Лемера работает следующим образом. Позволять M_п = 2^п - 1 будет числом Мерсенна для тестирования п ан нечетное простое число. Первобытность п можно эффективно проверить с помощью простого алгоритма, например судебное отделение поскольку п экспоненциально меньше, чем M_п. Определите последовательность ${ displaystyle {s_ {i} }}$ для всех я ≥ 0 по

${ displaystyle s_ {i} = { begin {cases} 4 & { text {if}} i = 0; s_ {i-1} ^ {2} -2 & { text {else.}} end {случаи}}}$

Первые несколько членов этой последовательности: 4, 14, 194, 37634, ... (последовательность A003010 в OEIS ).Потом M_п прост тогда и только тогда, когда

${ displaystyle s_ {p-2} Equiv 0 { pmod {M_ {p}}}.}$

Номер s_п − 2 модM_п называется Остаток Лукаса-Лемера из п. (Некоторые авторы эквивалентно устанавливают s₁ = 4 и test s_п−1 мод M_п). В псевдокод, тест можно записать как

// Определяем, если Mп = 2п - 1 является простым для п > 2Лукас – Лемер(п) вар s = 4 вар M = 2п − 1    повторение p - 2 раза: s = ((s × s) - 2) mod M если s == 0 возвращаться ОСНОВНОЙ еще возвращаться КОМПОЗИТНЫЙ

Выполнение мод M на каждой итерации гарантирует, что все промежуточные результаты будут не более п бит (в противном случае количество бит удваивается на каждой итерации). Та же стратегия используется в модульное возведение в степень.

Альтернативные начальные значения

Начальные значения s₀ кроме 4 возможны, например 10, 52 и другие (последовательность A018844 в OEIS ). Остаток Лукаса-Лемера, рассчитанный с этими альтернативными начальными значениями, все равно будет равен нулю, если M_п простое число Мерсенна. Однако члены последовательности будут другими, и ненулевой вычет Люка-Лемера для непростых M_п будет иметь числовое значение, отличное от ненулевого значения, рассчитанного при s₀ = 4.

Также можно использовать начальное значение (2 мод.M_п) (3 модM_п)⁻¹, обычно обозначается для краткости 2/3.^[1] Это начальное значение равно (2^п + 1) / 3, то Номер вагстаффа с показателем п.

Начальные значения, такие как 4, 10 и 2/3, универсальны, то есть они действительны для всех (или почти для всех) п. Есть бесконечно много дополнительных универсальных стартовых значений.^[1] Однако некоторые другие начальные значения действительны только для подмножества всех возможных п, Например s₀ = 3 можно использовать, если п = 3 (мод.4).^[2] Это начальное значение часто использовалось там, где это было удобно в эпоху ручных вычислений, в том числе Лукасом при доказательстве M₁₂₇ основной.^[3]Первые несколько членов последовательности: 3, 7, 47, ... (последовательность A001566 в OEIS ).

Знак предпоследнего семестра

Если s_п−2 = 0 модM_п тогда предпоследний член s_п−3 = ± 2^(п+1)/2 модM_п. Знак этого предпоследнего члена называется символом Лемера ϵ (s₀, п).

В 2000 году С.Ю. Гебре-Эгзиабер доказал, что для начального значения 2/3 и для п ≠ 5 знак:

${ Displaystyle epsilon ({2 более 3}, p) = (- 1) ^ {p-1 over 2}}$

То есть ϵ (2/3,п) = +1 тогда и только тогда п = 1 (mod 4) и p 5.^[1]

Тот же автор также доказал, что символы Лемера для начальных значений 4 и 10, когда п не 2 или 5 связаны между собой:

${ Displaystyle epsilon (10, p) = epsilon (4, p) times (-1) ^ {{(p + 1) (p + 3)} over 8}}$

То есть ϵ (4,п) × ϵ (10,п) = 1 тогда и только тогда. п = 5 или 7 (mod 8) и p ≠ 2, 5.^[1]

Последовательность OEIS A123271 показывает ϵ (4,п) для каждого простого числа Мерсенна M_п.

Сложность времени

В описанном выше алгоритме на каждой итерации выполняются две дорогостоящие операции: умножение с × с, а мод M операция. В мод M работа может быть особенно эффективной на стандартных двоичных компьютерах, если учесть, что

${ Displaystyle к эквив (к , { bmod {,}} 2 ^ {n}) + lfloor k / 2 ^ {n} rfloor { pmod {2 ^ {n} -1}}. }$

Это говорит о том, что наименее значимые п кусочки k плюс оставшиеся части k эквивалентны k по модулю 2^п−1. Эту эквивалентность можно использовать неоднократно, пока не более п биты остаются. Таким образом, остаток после деления k у Мерсенна номер 2^п−1 вычисляется без использования деления. Например,

Более того, поскольку с × с никогда не превысит M² < 2^2p, этот простой прием сходится не более чем за 1 п-битовое сложение (и, возможно, перенос из пth к 1-му биту), что может быть выполнено за линейное время. Этот алгоритм имеет небольшой исключительный случай. Будет произведено 2^п−1 для кратного модуля, а не для правильного значения 0. Однако этот случай легко обнаружить и исправить.

Если модуль не задан, асимптотическая сложность алгоритма зависит только от алгоритм умножения привык к квадрату s на каждом шагу. Простой "школьный" алгоритм умножения требует О (п²) операций на уровне битов или слов для возведения в квадрат п-битовое число. Поскольку это происходит O (п) раз, общая временная сложность O (п³). Более эффективный алгоритм умножения - это Алгоритм Шёнхаге – Штрассена, который основан на Быстрое преобразование Фурье. Это требует только O (п бревно п журнал журнал п) время возвести в квадрат п-битовое число. Это снижает сложность до O (п² бревно п журнал журнал п) или Õ (п²).^[4] Еще более эффективный алгоритм умножения, Алгоритм Фюрера, только нужно ${ Displaystyle р журнал р 2 ^ {О ( журнал ^ {*} р)}}$ время умножать два п-битовые числа.

Для сравнения, наиболее эффективный рандомизированный тест на простоту для общих целых чисел, Тест на простоту Миллера – Рабина, требует O (k п² бревно п журнал журнал п) битовые операции с использованием умножения БПФ для п-цифровой номер, где k - количество итераций, связанное с частотой ошибок. Для постоянного k, это тот же класс сложности, что и тест Лукаса-Лемера. Однако на практике стоимость выполнения множества итераций и других различий приводит к снижению производительности Миллера – Рабина. Самый эффективный детерминированный тест на простоту п-цифровой номер, Тест на простоту AKS, требует Õ (n⁶) битовые операции в своем наиболее известном варианте и очень медленные даже для относительно небольших значений.

Примеры

Число Мерсенна M₃ = 2³−1 = 7 простое число. Тест Лукаса – Лемера подтверждает это следующим образом. Первоначально s устанавливается на 4, а затем обновляется 3−2 = 1 раз:

• s ← ((4 × 4) - 2) mod 7 = 0.

Поскольку окончательное значение s равно 0, напрашивается вывод, что M₃ простое.

С другой стороны, M₁₁ = 2047 = 23 × 89 не является простым. Опять таки, s установлен на 4, но теперь обновляется 11−2 = 9 раз:

• s ← ((4 × 4) - 2) mod 2047 = 14
• s ← ((14 × 14) - 2) mod 2047 = 194
• s ← ((194 × 194) - 2) mod 2047 = 788
• s ← ((788 × 788) - 2) mod 2047 = 701
• s ← ((701 × 701) - 2) mod 2047 = 119
• s ← ((119 × 119) - 2) мод 2047 = 1877
• s ← ((1877 × 1877) - 2) мод 2047 = 240
• s ← ((240 × 240) - 2) мод 2047 = 282
• s ← ((282 × 282) - 2) mod 2047 = 1736

Поскольку окончательное значение s не 0, вывод состоит в том, что M₁₁ = 2047 не является простым. Хотя M₁₁ = 2047 имеет нетривиальные факторы, тест Лукаса – Лемера не дает никаких указаний на то, какими они могут быть.

Доказательство правильности

Доказательство правильности этого теста, представленное здесь, проще, чем исходное доказательство, данное Лемером. Напомним определение

${ displaystyle s_ {i} = { begin {cases} 4 & { text {if}} i = 0; s_ {i-1} ^ {2} -2 & { text {else.}} end {случаи}}}$

Цель - показать, что M_п премьер если только ${ displaystyle s_ {p-2} Equiv 0 { pmod {M_ {p}}}.}$

Последовательность ${ displaystyle { langle} s_ {i} { rangle}}$ это отношение повторения с закрытое решение. Позволять ${ displaystyle omega = 2 + { sqrt {3}}}$ и ${ displaystyle { bar { omega}} = 2 - { sqrt {3}}}$. Затем следует индукция который ${ displaystyle s_ {i} = omega ^ {2 ^ {i}} + { bar { omega}} ^ {2 ^ {i}}}$ для всех я:

${ displaystyle s_ {0} = omega ^ {2 ^ {0}} + { bar { omega}} ^ {2 ^ {0}} = left (2 + { sqrt {3}} right ) + left (2 - { sqrt {3}} right) = 4}$

и

${ displaystyle { begin {align} s_ {n} & = s_ {n-1} ^ {2} -2 & = left ( omega ^ {2 ^ {n-1}} + { bar { omega}} ^ {2 ^ {n-1}} right) ^ {2} -2 & = omega ^ {2 ^ {n}} + { bar { omega}} ^ {2 ^ {n}} + 2 ( omega { bar { omega}}) ^ {2 ^ {n-1}} - 2 & = omega ^ {2 ^ {n}} + { bar { omega}} ^ {2 ^ {n}}. end {align}}}$

Последний шаг использует ${ displaystyle omega { bar { omega}} = left (2 + { sqrt {3}} right) left (2 - { sqrt {3}} right) = 1.}$ Эта закрытая форма используется как при доказательстве достаточности, так и при доказательстве необходимости.

Достаточность

Цель - показать, что ${ Displaystyle s_ {p-2} Equiv 0 { pmod {M_ {p}}}}$ подразумевает, что ${ displaystyle M_ {p}}$ простое. Далее следует прямое доказательство, использующее элементарные теория групп предоставлено Дж. У. Брюсом^[5] как сообщает Джейсон Войцеховски.^[6]

Предполагать ${ displaystyle s_ {p-2} Equiv 0 { pmod {M_ {p}}}.}$ потом

${ displaystyle omega ^ {2 ^ {p-2}} + { bar { omega}} ^ {2 ^ {p-2}} = kM_ {p}}$

для некоторого целого числа k, так

${ displaystyle omega ^ {2 ^ {p-2}} = kM_ {p} - { bar { omega}} ^ {2 ^ {p-2}}.}$

Умножение на ${ displaystyle omega ^ {2 ^ {p-2}}}$ дает

${ displaystyle left ( omega ^ {2 ^ {p-2}} right) ^ {2} = kM_ {p} omega ^ {2 ^ {p-2}} - ( omega { bar { omega}}) ^ {2 ^ {p-2}}.}$

Таким образом,

${ Displaystyle omega ^ {2 ^ {p-1}} = kM_ {p} omega ^ {2 ^ {p-2}} - 1. qquad qquad (1)}$

От противоречия предположим, что M_п составно, и пусть q быть наименьшим простым делителем M_п. Числа Мерсенна нечетные, поэтому q > 2. Неофициально,^{[примечание 1]} позволять ${ displaystyle mathbb {Z} _ {q}}$ быть целыми числами по модулю q, и разреши ${ displaystyle X = left {a + b { sqrt {3}} mid a, b in mathbb {Z} _ {q} right }.}$ Умножение в ${ displaystyle X}$ определяется как

${ displaystyle left (a + { sqrt {3}} b right) left (c + { sqrt {3}} d right) = [(ac + 3bd) , { bmod {,}} q] + { sqrt {3}} [(ad + bc) , { bmod {,}} q].}$

Ясно, что это умножение замкнутое, т.е. произведение чисел из Икс сам находится в Икс. Размер Икс обозначается ${ displaystyle | X |.}$

С q > 2, следует, что ${ displaystyle omega}$ и ${ displaystyle { bar { omega}}}$ находятся в Икс.^{[заметка 2]} Подмножество элементов в Икс с обратными образует группу, которая обозначается Икс* и имеет размер ${ displaystyle | X ^ {*} |.}$ Один элемент в Икс не имеет обратного равно 0, поэтому ${ displaystyle | X ^ {*} | leq | X | -1 = q ^ {2} -1.}$

Сейчас же ${ Displaystyle M_ {p} Equiv 0 { pmod {q}}}$ и ${ displaystyle omega in X}$, так

${ displaystyle kM_ {p} omega ^ {2 ^ {p-2}} = 0}$

в Икс.Тогда по уравнению (1)

${ displaystyle omega ^ {2 ^ {p-1}} = - 1}$

в Икс, и возведение обеих сторон в квадрат дает

${ displaystyle omega ^ {2 ^ {p}} = 1.}$

Таким образом ${ displaystyle omega}$ лежит в Икс* и имеет обратный ${ displaystyle omega ^ {2 ^ {p} -1}.}$ Кроме того, порядок из ${ displaystyle omega}$ разделяет ${ displaystyle 2 ^ {p}.}$ тем не мение ${ Displaystyle omega ^ {2 ^ {p-1}} neq 1}$, поэтому порядок не разделяется ${ displaystyle 2 ^ {p-1}.}$ Таким образом, заказ ровно ${ displaystyle 2 ^ {p}.}$

Порядок элемента равен порядку (размеру) группы, поэтому

${ displaystyle 2 ^ {p} leq | X ^ {*} | leq q ^ {2} -1$

Но q - наименьший простой фактор композиции ${ displaystyle M_ {p}}$, так

${ displaystyle q ^ {2} leq M_ {p} = 2 ^ {p} -1.}$

Отсюда получаем противоречие ${ displaystyle 2 ^ {p} <2 ^ {p} -1}$. Следовательно, ${ displaystyle M_ {p}}$ простое.

Необходимость

В другом направлении цель состоит в том, чтобы показать, что первичность ${ displaystyle M_ {p}}$ подразумевает ${ Displaystyle s_ {p-2} эквив 0 { pmod {M_ {p}}}}$. Следующее упрощенное доказательство принадлежит Öystein J. Rödseth.^[7]

С ${ Displaystyle 2 ^ {p} -1 экв 7 { pmod {12}}}$ для нечетных ${ displaystyle p> 1}$, следует из свойства символа Лежандра который ${ displaystyle (3 | M_ {p}) = - 1.}$ Это означает, что 3 - это квадратичный невычет по модулю ${ displaystyle M_ {p}.}$ К Критерий Эйлера, это эквивалентно

${ displaystyle 3 ^ { frac {M_ {p} -1} {2}} Equiv -1 { pmod {M_ {p}}}.}$

Напротив, 2 - это квадратичный вычет по модулю ${ displaystyle M_ {p}}$ поскольку ${ Displaystyle 2 ^ {p} Equiv 1 { pmod {M_ {p}}}}$ и так ${ Displaystyle 2 Equiv 2 ^ {p + 1} = left (2 ^ { frac {p + 1} {2}} right) ^ {2} { pmod {M_ {p}}}.}$ На этот раз критерий Эйлера дает

${ displaystyle 2 ^ { frac {M_ {p} -1} {2}} Equiv 1 { pmod {M_ {p}}}.}$

Объединение этих двух отношений эквивалентности дает

${ displaystyle 24 ^ { frac {M_ {p} -1} {2}} Equiv left (2 ^ { frac {M_ {p} -1} {2}} right) ^ {3} left (3 ^ { frac {M_ {p} -1} {2}} right) Equiv (1) ^ {3} (- 1) Equiv -1 { pmod {M_ {p}}}. }$

Позволять ${ displaystyle sigma = 2 { sqrt {3}}}$, и определим Икс как прежде, как кольцо ${ displaystyle X = {a + b { sqrt {3}} mid a, b in mathbb {Z} _ {M_ {p}} }.}$ Тогда на ринге Икс, следует, что

${ displaystyle { begin {align} (6+ sigma) ^ {M_ {p}} & = 6 ^ {M_ {p}} + left (2 ^ {M_ {p}} right) left ( { sqrt {3}} ^ {M_ {p}} right) & = 6 + 2 left (3 ^ { frac {M_ {p} -1} {2}} right) { sqrt {3}} & = 6 + 2 (-1) { sqrt {3}} & = 6- sigma, end {align}}}$

где первое равенство использует Биномиальная теорема в конечном поле, который

${ displaystyle (x + y) ^ {M_ {p}} Equiv x ^ {M_ {p}} + y ^ {M_ {p}} { pmod {M_ {p}}}}$,

а второе равенство использует Маленькая теорема Ферма, который

${ displaystyle a ^ {M_ {p}} Equiv a { pmod {M_ {p}}}}$

для любого целого а. Значение ${ displaystyle sigma}$ было выбрано так, что ${ displaystyle omega = { frac {(6+ sigma) ^ {2}} {24}}.}$ Следовательно, это можно использовать для вычисления ${ displaystyle omega ^ { frac {M_ {p} +1} {2}}}$ в ринге Икс в качестве

${ displaystyle { begin {align} omega ^ { frac {M_ {p} +1} {2}} & = { frac {(6+ sigma) ^ {M_ {p} +1}} { 24 ^ { frac {M_ {p} +1} {2}}}} & = { frac {(6+ sigma) (6+ sigma) ^ {M_ {p}}} {24 cdot 24 ^ { frac {M_ {p} -1} {2}}}} & = { frac {(6+ sigma) (6- sigma)} {- 24}} & = -1. End {выравнивается}}}$

Остается только умножить обе части этого уравнения на ${ displaystyle { bar { omega}} ^ { frac {M_ {p} +1} {4}}}$ и использовать ${ displaystyle omega { bar { omega}} = 1}$, который дает

${ displaystyle { begin {align} omega ^ { frac {M_ {p} +1} {2}} { bar { omega}} ^ { frac {M_ {p} +1} {4} } & = - { bar { omega}} ^ { frac {M_ {p} +1} {4}} omega ^ { frac {M_ {p} +1} {4}} + { bar { omega}} ^ { frac {M_ {p} +1} {4}} & = 0 omega ^ { frac {2 ^ {p} -1 + 1} {4}} + { bar { omega}} ^ { frac {2 ^ {p} -1 + 1} {4}} & = 0 omega ^ {2 ^ {p-2}} + { bar { omega}} ^ {2 ^ {p-2}} & = 0 s_ {p-2} & = 0. end {align}}}$

С ${ displaystyle s_ {p-2}}$ 0 в Икс, это также 0 по модулю ${ displaystyle M_ {p}.}$

Приложения

Тест Лукаса – Лемера - это критерий простоты, используемый Отличный Интернет-поиск Mersenne Prime (GIMPS), чтобы найти большие простые числа. Этот поиск оказался успешным в обнаружении многих из известных на сегодняшний день самых больших простых чисел.^[8] Тест считается ценным, потому что он, вероятно, может проверить простоту большого набора очень больших чисел за доступное время. Напротив, столь же быстрый Тест Пепина для любого Число Ферма может использоваться только для гораздо меньшего набора очень больших чисел до достижения вычислительных ограничений.

Смотрите также

• Гипотеза Мерсенна
• Тест Лукаса-Лемера-Ризеля

Примечания

Рекомендации

• Крэндалл, Ричард; Померанс, Карл (2001), «Раздел 4.2.1: Тест Лукаса – Лемера», Простые числа: вычислительная перспектива (1-е изд.), Берлин: Springer, стр. 167–170, ISBN  0-387-94777-9

внешняя ссылка

• Вайсштейн, Эрик В. «Тест Лукаса – Лемера». MathWorld.
• GIMPS (Великий поиск Мерсенна Прайма в Интернете)
• Доказательство теста Лукаса – Лемера – Рейкса (для чисел Ферма)
• Тест Лукаса-Лемера в MersenneWiki