В математике , то тест Лукас-Лехмер ( ЛЛТ ) представляет собой тест на простоту для чисел Мерсенна . Первоначально тест был разработан Эдуардом Лукасом в 1856 году [ необходима цитата ] и впоследствии улучшен Лукасом в 1878 году и Дерриком Генри Лемером в 1930-х годах.
Тест
Тест Лукаса – Лемера работает следующим образом. Пусть М р = 2 р - 1 быть номером Мерсенн испытанию с р нечетное простое число . Простота p может быть эффективно проверена с помощью простого алгоритма, такого как пробное деление, поскольку p экспоненциально меньше M p . Определите последовательностьдля всех i ≥ 0 по
Первые несколько членов этой последовательности - 4, 14, 194, 37634, ... (последовательность A003010 в OEIS ). Тогда M p является простым тогда и только тогда, когда
Число s p - 2 mod M p называется вычетом Люка – Лемера числа p . (Некоторые авторы эквивалентно полагают s 1 = 4 и проверяют s p −1 mod M p ). В псевдокоде тест можно записать как
// Определяем, является ли M p = 2 p - 1 простым для p > 2 Lucas – Lehmer (p) var s = 4 var M = 2 p - 1 повторение p - 2 раза: s = ((s × s) - 2) mod M если s == 0 вернуть PRIME иначе вернуть КОМПОЗИТНЫЙ
Выполнение mod M
на каждой итерации гарантирует, что все промежуточные результаты будут иметь не более p битов (в противном случае количество битов удваивается на каждой итерации). Та же стратегия используется в модульном возведении в степень .
Альтернативные начальные значения
Возможны начальные значения s 0, отличные от 4, например 10, 52 и другие (последовательность A018844 в OEIS ). Вычет Лукаса-Лемера, вычисленный с этими альтернативными начальными значениями, все равно будет равен нулю, если M p является простым числом Мерсенна. Однако члены последовательности будут другими, и ненулевой остаток Люка-Лемера для непростого M p будет иметь числовое значение, отличное от ненулевого значения, вычисленного при s 0 = 4.
Также возможно использовать начальное значение (2 mod M p ) (3 mod M p ) -1 , обычно обозначаемое для краткости 2/3. [1] Это начальное значение равно (2 p + 1) / 3, числу Вагстаффа с показателем p .
Начальные значения, такие как 4, 10 и 2/3, универсальны, то есть они действительны для всех (или почти всех) p . Есть бесконечно много дополнительных универсальных стартовых значений. [1] Однако некоторые другие начальные значения действительны только для подмножества всех возможных p , например s 0 = 3 можно использовать, если p = 3 (mod 4). [2] Это начальное значение часто использовалось там, где это было удобно, в эпоху ручных вычислений, в том числе Лукасом при доказательстве простого числа M 127 . [3] Первые несколько членов последовательности - 3, 7, 47, ... (последовательность A001566 в OEIS ).
Знак предпоследнего семестра
Если s p −2 = 0 mod M p, то предпоследний член равен s p −3 = ± 2 ( p +1) / 2 mod M p . Знак этого предпоследнего члена называется символом Лемера ϵ ( s 0 , p ).
В 2000 г. С.Ю. Гебре-Эгзиабхер доказал, что для начального значения 2/3 и для p ≠ 5 знак имеет вид:
То есть ϵ (2/3, p ) = +1 тогда и только тогда, когда p = 1 (mod 4) и p ≠ 5. [1]
Тот же автор также доказал, что символы Лемера для начальных значений 4 и 10, когда p не равно 2 или 5, связаны следующим образом:
То есть ϵ (4, p ) × ϵ (10, p ) = 1, если p = 5 или 7 (mod 8) и p) 2, 5. [1]
Последовательность OEIS A123271 показывает ϵ (4, p ) для каждого простого числа Мерсенна M p .
Сложность времени
В описанном выше алгоритме на каждой итерации выполняются две дорогостоящие операции: умножение s × s
и mod M
операция. mod M
Операция может быть особенно эффективным на стандартных бинарных компьютерах, заметив , что
Это говорит о том, что младшие n битов k плюс оставшиеся биты k эквивалентны k по модулю 2 n -1. Эту эквивалентность можно использовать многократно, пока не останется не более n битов. Таким образом, остаток от деления k на число Мерсенна 2 n -1 вычисляется без использования деления. Например,
916 по модулю 2 5 −1 | знак равно | 1110010100 2 мод 2 5 −1 |
знак равно | ((916 mod 2 5 ) + int (916 ÷ 2 5 )) mod 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
никогда не превысит M 2 <2 2p , этот простой метод сводится к сложению не более 1 p- бита (и, возможно, переносу с p- го бита на 1-й бит), что может быть выполнено за линейное время. Этот алгоритм имеет небольшой исключительный случай. Это даст 2 n -1 для кратного модуля, а не правильного значения 0. Однако этот случай легко обнаружить и исправить.
При отсутствии модуля асимптотическая сложность алгоритма зависит только от алгоритма умножения, используемого для возведения s в квадрат на каждом шаге. Простой "школьный" алгоритм умножения требует O ( p 2 ) операций на уровне битов или слов для возведения в квадрат p -битного числа. Поскольку это происходит O ( p ) раз, общая временная сложность составляет O ( p 3 ). Более эффективный алгоритм умножения - это алгоритм Шёнхаге – Штрассена , который основан на быстром преобразовании Фурье . Требуется только время O ( p log p log log p ), чтобы возвести p- битное число в квадрат . Это снижает сложность до O ( p 2 log p log log p ) или Õ ( p 2 ). [4] Еще более эффективный алгоритм умножения, алгоритм Фюрера , требует тольковремя умножить два p- битных числа.
Для сравнения, наиболее эффективный рандомизированный тест на простоту для общих целых чисел, тест на простоту Миллера-Рабина , требует O ( k n 2 log n log log n ) битовых операций с использованием умножения БПФ для n- значного числа, где k - количество итераций и связан с частотой ошибок. Для постоянного k это тот же класс сложности, что и тест Лукаса-Лемера. Однако на практике стоимость выполнения множества итераций и других различий приводит к снижению производительности Миллера – Рабина. Самый эффективный детерминированный тест на простоту для любого n- значного числа, тест на простоту AKS , требует Õ (n 6 ) битовых операций в его наиболее известном варианте и является чрезвычайно медленным даже для относительно небольших значений.
Примеры
Число Мерсенна M 3 = 2 3 −1 = 7 простое. Тест Лукаса – Лемера подтверждает это следующим образом. Первоначально s установлено на 4, а затем обновляется 3−2 = 1 раз:
- s ← ((4 × 4) - 2) mod 7 = 0.
Поскольку окончательное значение s равно 0, можно сделать вывод, что M 3 простое число.
С другой стороны, M 11 = 2047 = 23 × 89 не является простым. Опять же, s установлено в 4, но теперь обновляется 11−2 = 9 раз:
- s ← ((4 × 4) - 2) mod 2047 = 14
- s ← ((14 × 14) - 2) мод 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 11 = 2047 не является простым числом. Хотя M 11 = 2047 имеет нетривиальные множители, тест Лукаса – Лемера не дает никаких указаний на то, какими они могут быть.
Доказательство правильности
Доказательство правильности этого теста, представленное здесь, проще, чем исходное доказательство, данное Лемером. Напомним определение
Цель состоит в том, чтобы показать, что M p простое тогда и только тогда, когда
Последовательность является рекуррентным соотношением с замкнутым решением . Позволять а также . Тогда по индукции следует, чтодля всех я :
а также
Последний шаг использует Эта закрытая форма используется как при доказательстве достаточности, так и при доказательстве необходимости.
Достаточность
Цель - показать, что подразумевает, что простое. Далее следует прямое доказательство, использующее элементарную теорию групп, данное Дж. У. Брюсом [5] и изложенное Джейсоном Войцеховским. [6]
Предполагать потом
для некоторого целого k , поэтому
Умножение на дает
Таким образом,
От противного, предположим, что M p составное, и пусть q - наименьший простой делитель M p . Числа Мерсенна нечетные, поэтому q > 2. Неформально [примечание 1] пусть- целые числа по модулю q , и пусть Умножение в определяется как
Очевидно, что это умножение замкнуто, то есть произведение чисел из X сам в X . Размер X обозначается
Поскольку q > 2, то а также в X . [примечание 2] Подмножество элементов в X с инверсиями образует группу, которая обозначается X * и имеет размерОдин элемент в X , у которого нет обратного, равен 0, поэтому
Сейчас а также , так
в X . Тогда по уравнению (1)
в X , и возведение в квадрат обеих сторон дает
Таким образом лежит в X * и имеет обратныйКроме того, порядок из разделяет тем не мение , поэтому порядок не разделяется Таким образом, заказ ровно
Порядок элемента равен порядку (размеру) группы, поэтому
Но q - наименьший простой фактор композиции, так
Это приводит к противоречию . Следовательно, простое.
Необходимость
С другой стороны, цель - показать, что первобытность подразумевает . Следующее упрощенное доказательство принадлежит Öystein J. Rödseth. [7]
С для нечетных , из свойств символа Лежандра следует, чтоЭто означает, что 3 - квадратичный невычет по модулюПо критерию Эйлера это эквивалентно
Напротив, 2 - квадратичный вычет по модулю поскольку и другие На этот раз критерий Эйлера дает
Объединение этих двух отношений эквивалентности дает
Позволять , и определим X, как и раньше, как кольцоТогда в кольце X следует, что
где первое равенство использует биномиальную теорему в конечном поле , которое имеет вид
- ,
а во втором равенстве используется малая теорема Ферма :
для любого целого числа a . Значение было выбрано так, что Следовательно, это можно использовать для вычисления в кольце X как
Остается только умножить обе части этого уравнения на и использовать , который дает
С равен 0 в X , он также равен 0 по модулю
Приложения
Тест Лукаса-Лемера - это тест на простоту, используемый Большим поиском простых чисел Мерсенна в Интернете (GIMPS) для поиска больших простых чисел. Этот поиск оказался успешным в обнаружении многих из известных на сегодняшний день самых больших простых чисел. [8] Тест считается ценным, потому что он, вероятно, может проверить простоту большого набора очень больших чисел в течение доступного промежутка времени. Напротив, эквивалентно быстрый тест Пепена для любого числа Ферма можно использовать только на гораздо меньшем наборе очень больших чисел до достижения вычислительных пределов.
Смотрите также
- Гипотеза Мерсенна
- Тест Лукаса-Лемера-Ризеля
Заметки
- ^ Формально пусть а также .
- ^ Формально а также в X . Злоупотреблением языком а также отождествляются со своими образами в X при естественном гомоморфизме колец изв X, который отправляетк Т .
Рекомендации
- ^ а б в г Янсен, BJH (2012). Простые числа Мерсенна и теория полей классов (докторская диссертация). Лейденский университет. п. iii . Проверено 17 декабря 2018 .
- ^ Робинсон, Рафаэль М. (1954). «Числа Мерсенна и Ферма» . Proc. Амер. Математика. Soc . 5 : 842–846. DOI : 10.1090 / S0002-9939-1954-0064787-4 .
- ^ Хаворт, Гай (1990). Числа Мерсенна (PDF) (Технический отчет). п. 20 . Проверено 17 декабря 2018 .
- ^ Колкитт, Вашингтон; Welsh, Л., младший (1991), «Новый Мерсенна», Математика вычислений , 56 (194): 867-870, DOI : 10,2307 / 2008415 ,
использование БПФА ускоряет асимптотическое время для Лукаса –Тест Лемера для M p от O ( p 3 ) до O ( p 2 log p log log p ) битовых операций.
- ^ Брюс, JW (1993). «Действительно тривиальное доказательство теста Лукаса – Лемера». Американский математический ежемесячник . 100 (4): 370–371. DOI : 10.2307 / 2324959 .
- ^ Джейсон Войцеховски. Простые числа Мерсенна, введение и обзор . 2003 г.
- ^ Рёдсет, Ойстейн Дж. (1994). «Заметка о проверках простоты для N = h · 2 ^ n − 1» (PDF) . BIT Численная математика . 34 (3): 451–454. DOI : 10.1007 / BF01935653 . Архивировано из оригинального (PDF) 6 марта 2016 года.
- ^ "Десять лучших" рекордов простых чисел , основные страницы
- Крэндалл, Ричард ; Померанс, Карл (2001), «Раздел 4.2.1: тест Лукаса – Лемера», Простые числа: вычислительная перспектива (1-е изд.), Берлин: Springer, стр. 167–170, ISBN 0-387-94777-9
Внешние ссылки
- Вайсштейн, Эрик В. «Тест Лукаса – Лемера» . MathWorld .
- GIMPS (Великий поиск Мерсенна Прайма в Интернете)
- Доказательство теста Лукаса – Лемера – Рейкса (для чисел Ферма).
- Тест Лукаса-Лемера в MersenneWiki