Тест простоты Люка-Лемера

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

В математике тест Люка-Лемера ( 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 ). Тогда M _p является простым тогда и только тогда, когда

${\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 раза: с = ((с × с) − 2) mod M если s == 0 вернуть ПРОСТОЙ , иначе  вернуть СОСТАВНОЙ

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

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

Возможны начальные значения s _{0 , отличные от 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 _127. ^[4] Первые несколько членов последовательности — это 3, 7, 47, ... (последовательность A001566 в OEIS ).

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

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

Тот же автор также доказал гипотезу Вольтмана [ ^5] о том, что символы Лемера для начальных значений 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 (mod 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 вычисляется без использования деления. Например,

Более того, поскольку s × sникогда не превысит M ² < 2 ^2p , этот простой метод сходится максимум за 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 ² ). ^[6] Еще более эффективный алгоритм умножения, алгоритм Фюрера , требует времени только для умножения двух 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, вывод состоит в том, что M3 _— простое число.

С другой стороны, 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.}$

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

Цель состоит в том, чтобы показать, что влечет, что является простым числом. Далее следует простое доказательство, использующее элементарную теорию групп, данную Дж. В. Брюсом ^[7], как изложено Джейсоном Войцеховским. ^[8] ${\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}$

в X. Тогда по уравнению (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}}$

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

В другом направлении цель состоит в том, чтобы показать, что простота влечет . Следующее упрощенное доказательство принадлежит Öystein J. Rödseth. ^[9] ${\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}}}$

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

Приложения

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

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

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

Примечания

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, который отправляет в T. ${\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. Jaroma, John H. (2004). "Note on the Lucas–Lehmer Test" (PDF) . Бюллетень Ирландского математического общества . 54 (2). Ирландское математическое общество: 63. doi :10.33232/BIMS.0054.63.72. S2CID  16831811.
2. Jansen, BJH (2012). Простые числа Мерсенна и теория полей классов (Докторская диссертация). Лейденский университет. стр. iii–iv . Получено 17.12.2018 .
3. Робинсон, Рафаэль М. (1954). «Числа Мерсенна и Ферма». Proc. Amer. Math. Soc . 5 (5): 842–846. doi : 10.1090/S0002-9939-1954-0064787-4 .
4. Хаворт, Гай (1990). Числа Мерсенна (PDF) (Технический отчет). стр. 20. Получено 17.12.2018 .
5. Lenstra, Jr., HW (2001-05-13). Buhler, J.; Niederreiter, H.; Pohst, ME (ред.). Гипотеза Вольтмана о тесте Лукаса-Лемера (PDF) . Алгоритмы и теория чисел. стр. 20. Получено 2024-10-16 .
6. Колкитт, В. Н.; Уэлш, Л. младший (1991), «Новое простое число Мерсенна», Математика вычислений , 56 (194): 867–870, doi : 10.2307/2008415 , JSTOR  2008415, Использование БПФ ускоряет асимптотическое время теста Лукаса–Лемера для M _p с O( p ³ ) до O( p ² log p log log p ) битовых операций.
7. Брюс, Дж. В. (1993). «Действительно тривиальное доказательство теста Лукаса–Лемера». The American Mathematical Monthly . 100 (4): 370–371. doi :10.2307/2324959. JSTOR  2324959.
8. Джейсон Войцеховски. Простые числа Мерсенна, введение и обзор. 2003.
9. Rödseth, Öystein J. (1994). "A note on primality tests for N=h·2^n−1" (PDF) . BIT Numerical Mathematics . 34 (3): 451–454. doi :10.1007/BF01935653. S2CID  120438959. Архивировано из оригинала (PDF) 6 марта 2016 г.
10. "Десять лучших" записей Primes, The Prime Pages

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

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

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