Тест Лукаса-Лемера на простоту

Эта статья о тесте Лукаса-Лемера, который применим только к числам Мерсенна. Информацию о тесте Люка-Лемера, применимом к натуральному числу n , см. в разделе «Тест на простоту Люка» . Чтобы узнать о тесте Лукаса-Лемера-Ризеля, см. Тест Лукаса-Лемера-Ризеля .

В математике тест Люка-Лемера ( LLT ) представляет собой тест на простоту чисел Мерсенна . Первоначально тест был разработан Эдуардом Лукасом в 1878 году. и впоследствии было доказано Дерриком Генри Лемером в 1930 году.

Тест

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

$s_{i}={\begin{cases}4&{\text{if }}i=0;\\s_{i-1}^{2}-2&{\text{otherwise.}}\end{cases}}$

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

$s_{p-2}\equiv 0{\pmod {M_{p}}}.$

Число s _{p − 2} mod M _p называется остатком Люка–Лемера числа p . (Некоторые авторы аналогичным образом устанавливают s ₁ = 4 и проверяют s _{p −1} mod M _p ). В псевдокоде тест может быть записан как

// Determine if Mp = 2p − 1 is prime for p > 2
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

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

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

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

Также можно использовать начальное значение (2 mod M _p )(3 mod M _p ) ⁻¹ , обычно для краткости обозначается 2/3. Это начальное значение равно (2 ^п + 1) /3 — число Вагстафа с показателем p .

Начальные значения, такие как 4, 10 и 2/3, являются универсальными, то есть они действительны для всех (или почти всех) p . Существует бесконечно много дополнительных универсальных стартовых значений. Однако некоторые другие начальные значения действительны только для подмножества всех возможных p , например, s ₀ = 3 можно использовать, если p = 3 (mod 4). Это начальное значение часто использовалось там, где это было возможно, в эпоху ручных вычислений, в том числе Лукасом при доказательстве простого числа М ₁₂₇ . Первые несколько членов последовательности — 3, 7, 47,... (последовательность A001566 в OEIS ).

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

Если s _{p −2} = 0 mod M _p , то предпоследний член равен s _{p −3} = ± 2. ^{( р +1)/2} мод М _п . Знак этого предпоследнего слагаемого называется символом Лемера ϵ( , _s0 p ) .

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

$\epsilon ({2 \over 3},\ p)=(-1)^{p-1 \over 2}$

То есть ϵ(2/3, p ) = +1, если p = 1 (mod 4) и p ≠ 5.

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

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

То есть ϵ(4, p ) × ϵ(10, p ) = 1, если p = 5 или 7 (mod 8) и p ≠ 2, 5.

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

Временная сложность

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

$k\equiv (k\,{\bmod {\,}}2^{n})+\lfloor k/2^{n}\rfloor {\pmod {2^{n}-1}}.$

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

916 против 2 5 −1	=	1110010100 2 против 2 5 −1
	=	((916 против 2 5 ) + int(916 ÷ 2 5 )) против 2 5 −1
	=	(10100 2 + 11100 2 ) против 2 5 −1
	=	110000 2 на 2 5 −1
	=	(10000 2 + 1 2 ) против 2 5 −1
	=	10001 2 против 2 5 −1
	=	10001 2
	=	17.

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

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

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

Примеры

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

• s ← ((4 × 4) − 2) по модулю 7 = 0.

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

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

• s ← ((4 × 4) − 2) по модулю 2047 = 14
• s ← ((14 × 14) − 2) по модулю 2047 = 194
• s ← ((194 × 194) − 2) по модулю 2047 = 788
• s ← ((788 × 788) − 2) по модулю 2047 = 701
• s ← ((701 × 701) − 2) по модулю 2047 = 119
• s ← ((119 × 119) − 2) по модулю 2047 = 1877
• с ← ((1877 × 1877) − 2) по модулю 2047 = 240
• s ← ((240 × 240) − 2) по модулю 2047 = 282
• s ← ((282 × 282) − 2) по модулю 2047 = 1736

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

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

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

$s_{i}={\begin{cases}4&{\text{if }}i=0;\\s_{i-1}^{2}-2&{\text{otherwise.}}\end{cases}}$

Цель состоит в том, чтобы показать, что M _p является простым тогда и только тогда, когда $s_{p-2}\equiv 0{\pmod {M_{p}}}.$

Последовательность ${\langle }s_{i}{\rangle }$ представляет собой рекуррентное отношение с решением в замкнутой форме . Позволять $\omega =2+{\sqrt {3}}$ и ${\bar {\omega }}=2-{\sqrt {3}}$. Тогда по индукции следует, что $s_{i}=\omega ^{2^{i}}+{\bar {\omega }}^{2^{i}}$ для всех я :

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

и

${\begin{aligned}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{aligned}}$

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

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

Цель – показать, что $s_{p-2}\equiv 0{\pmod {M_{p}}}$ подразумевает, что $M_{p}$ является простым. Далее следует простое доказательство, использующее элементарную теорию групп , данное Дж. У. Брюсом. как рассказал Джейсон Войцеховски.

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

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

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

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

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

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

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

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

В качестве противоречия предположим, что M _p является составным, и пусть q — наименьший простой делитель M _p . Числа Мерсенна нечетны, поэтому q > 2. Пусть $\mathbb {Z} _{q}$ — целые числа по модулю q , и пусть $X=\left\{a+b{\sqrt {3}}\mid a,b\in \mathbb {Z} _{q}\right\}.$ Умножение в $X$ определяется как

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

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

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

Сейчас $M_{p}\equiv 0{\pmod {q}}$ и $\omega \in X$, так

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

в Х. ​ Тогда по уравнению (1)

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

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

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

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

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

$2^{p}\leq |X^{*}|\leq q^{2}-1<q^{2}.$

Но q - наименьший простой делитель составного числа. $M_{p}$, так

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

Это приводит к противоречию $2^{p}<2^{p}-1$. Поэтому, $M_{p}$ является простым.

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

В другом направлении цель состоит в том, чтобы показать, что простота $M_{p}$ подразумевает $s_{p-2}\equiv 0{\pmod {M_{p}}}$. Следующее упрощенное доказательство принадлежит Ойстейну Дж. Рёдсету.

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

$3^{\frac {M_{p}-1}{2}}\equiv -1{\pmod {M_{p}}}.$

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

$2^{\frac {M_{p}-1}{2}}\equiv 1{\pmod {M_{p}}}.$

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

$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}}}.$

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

${\begin{aligned}(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{aligned}}$

где первое равенство использует биномиальную теорему в конечном поле , которое

$(x+y)^{M_{p}}\equiv x^{M_{p}}+y^{M_{p}}{\pmod {M_{p}}}$,

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

$a^{M_{p}}\equiv a{\pmod {M_{p}}}$

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

${\begin{aligned}\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{aligned}}$

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

${\begin{aligned}\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{aligned}}$

С $s_{p-2}$ равно 0 в X , оно также равно 0 по модулю $M_{p}.$

Приложения

Тест Лукаса-Лемера — один из основных тестов на простоту, используемый Великим интернет-поиском простых чисел Мерсенна (GIMPS) для поиска больших простых чисел. Этот поиск увенчался успехом и позволил обнаружить многие из самых больших простых чисел, известных на сегодняшний день. Этот тест считается ценным, поскольку с его помощью можно доказуемо проверить на простоту большой набор очень больших чисел за доступный промежуток времени. Напротив, столь же быстрый тест Пепена для любого числа Ферма можно использовать только для гораздо меньшего набора очень больших чисел, прежде чем он достигнет вычислительных пределов.

См. также

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

Ссылки

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

Внешние ссылки

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