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

Проверить, является ли число Мерсенна простым

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

Тест

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

${\displaystyle 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 _{является} простым тогда и только тогда, когда

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

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

// Определить, является ли M p = 2 p − 1 простым для p > 2 Лукас–Лемер (p) var s = 4 var M = 2 p − 1 повторяем p − 2 раза: s = ((s × s) − 2) mod M если s == 0, возвращаем PRIME , иначе  возвращаем COMPOSITE.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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 вычисляется без использования деления. Например,

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

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

Для сравнения, наиболее эффективный рандомизированный тест на простоту для общих целых чисел, тест на простоту Миллера-Рабина , требует O( k n ² log n log log 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 имеет нетривиальные факторы, тест Лукаса-Лемера не дает никаких указаний на то, какими они могут быть.

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

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

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

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

Последовательность представляет собой рекуррентное отношение с решением в замкнутой форме . Пусть и . Тогда по индукции следует , что для всех i : ${\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{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}}}$

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

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

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

Предположим, тогда ${\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 _p является составным, и пусть q — наименьший простой делитель M _p . Числа Мерсенна нечетны, поэтому q  > 2. Пусть – целые числа по модулю q , и пусть умножение в определяется как ${\displaystyle \mathbb {Z} _{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].}$^{[примечание 1]}

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

Поскольку q  > 2, то и находятся в X . ^{[примечание 2]} Подмножество элементов в X с обратными образует группу, которая обозначается X * и имеет размер. Один элемент в X , который не имеет обратного, равен 0, поэтому ${\displaystyle \omega }$ ${\displaystyle {\bar {\omega }}}$ ${\displaystyle |X^{*}|.}$ ${\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}$

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

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

Таким образом, лежит в X * и имеет обратный Кроме того, порядок делит Однако , поэтому порядок не делит Таким образом, порядок в точности равен ${\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^{2}.}$

Но q — наименьший простой делитель композиции , поэтому ${\displaystyle M_{p}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поскольку в X это 0 , оно также равно 0 по модулю. ${\displaystyle s_{p-2}}$ ${\displaystyle M_{p}.}$

Приложения

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

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

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

Примечания

1. Формально пусть и . ${\displaystyle \mathbb {Z} _{q}=\mathbb {Z} /q\mathbb {Z} }$ ${\displaystyle X=\mathbb {Z} _{q}[T]/\langle T^{2}-3\rangle }$
2. Формально и находятся в X. Злоупотреблением языком и отождествляются со своими образами в X при естественном гомоморфизме колец из в X , который переводит в Т. ${\displaystyle \omega +\langle T^{2}-3\rangle }$ ${\displaystyle {\bar {\omega }}+\langle T^{2}-3\rangle }$ ${\displaystyle \omega }$ ${\displaystyle {\bar {\omega }}}$ ${\displaystyle \mathbb {Z} [{\sqrt {3}}]}$ ${\displaystyle {\sqrt {3}}}$

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

1. Джарома, Джон Х. (2004). «Примечание к тесту Лукаса-Лемера» (PDF) . Бюллетень Ирландского математического общества . 54 (2). Ирландское математическое общество: 63. doi : 10.33232/BIMS.0054.63.72. S2CID  16831811.
2. Янсен, BJH (2012). Простые числа Мерсенна и теория полей классов (Докторская диссертация). Лейденский университет. п. iii . Проверено 17 декабря 2018 г.
3. Робинсон, Рафаэль М. (1954). «Числа Мерсенна и Ферма». Учеб. амер. Математика. Соц . 5 (5): 842–846. дои : 10.1090/S0002-9939-1954-0064787-4 .
4. Хаворт, Гай (1990). Числа Мерсенна (PDF) (Технический отчет). п. 20 . Проверено 17 декабря 2018 г.
5. Колкитт, Западная Нью-Йорк; Уэлш, Л. младший (1991), «Новое простое число Мерсенна», Mathematics of Computation , 56 (194): 867–870, doi : 10.2307/2008415 , JSTOR  2008415, Использование БПФ ускоряет асимптотическое время для тест Люка-Лемера для M _p от O( p ³ ) до O( p ² log p log log p ) битовых операций.
6. Брюс, JW (1993). «Действительно тривиальное доказательство теста Лукаса-Лемера». Американский математический ежемесячник . 100 (4): 370–371. дои : 10.2307/2324959. JSTOR  2324959.
7. Джейсон Войцеховски. Простые числа Мерсенна, введение и обзор. 2003.
8. Рёдсет, Эйстейн Дж. (1994). «Заметка о тестах на простоту для N=h·2^n−1» (PDF) . БИТ Численная математика . 34 (3): 451–454. дои : 10.1007/BF01935653. S2CID  120438959. Архивировано из оригинала (PDF) 6 марта 2016 г.
9. "Десять лучших" рекордных праймов, The Prime Pages

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

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

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