Тест Лукаса-Лемера-Ризеля
Тест на определение, является ли число простым

В математике тест Лукаса–Лемера–Ризела — это тест на простоту для чисел вида N  =  k  ⋅ 2 n  − 1 с нечетным k  < 2 n . Тест был разработан Гансом Ризелем и основан на тесте на простоту Лукаса–Лемера . Это самый быстрый детерминированный алгоритм, известный для чисел такого вида. [ необходима цитата ] Для чисел вида N  =  k  ⋅ 2 n  + 1 ( числа Прота ) используются либо применение теоремы Прота ( алгоритм Лас-Вегаса ), либо одно из детерминированных доказательств, описанных в Brillhart–Lehmer–Selfridge 1975 [1] (см. тест на простоту Поклингтона ).

Алгоритм

Алгоритм очень похож на тест Лукаса–Лемера , но с переменной начальной точкой в ​​зависимости от значения k .

Определим последовательность u i для всех i  > 0 следующим образом:

ты я = ты я − 1 2 − 2. {\displaystyle u_{i}=u_{i-1}^{2}-2.\,}

Тогда N  =  k  ⋅ 2 n  − 1, где k  < 2 n является простым числом тогда и только тогда, когда оно делит  u n −2 .

Нахождение начального значения

Начальное значение u 0 определяется следующим образом.

  • Если k ≡ 1 или 5 (mod 6): если 1 (mod 6) и n четное, или 5 (mod 6) и n нечетное, то 3 делит N, и нет необходимости в проверке. В противном случае N ≡ 7 (mod 24) и можно использовать последовательность Лукаса V(4,1): мы берем , что является k- м членом этой последовательности. Это обобщение обычного теста Лукаса–Лемера и сводится к нему при k = 1. ты 0 = ( 2 + 3 ) к + ( 2 − 3 ) к {\displaystyle u_{0}=(2+{\sqrt {3}})^{k}+(2-{\sqrt {3}})^{k}}
  • В противном случае мы оказываемся в случае, когда k кратно 3, и выбрать правильное значение u 0 сложнее . Известно, что если k = 3 и n ≡ 0 или 3 (mod 4), то можно взять u 0 = 5778.

Альтернативный метод нахождения начального значения u 0 приведен в Rödseth 1994. [2] Метод выбора гораздо проще, чем тот, который использовал Ризель для случая 3 делит k . Сначала найдем значение P , которое удовлетворяет следующим равенствам символов Якоби :

( П − 2 Н ) = 1 и ( П + 2 Н ) = − 1 {\displaystyle \left({\frac {P-2}{N}}\right)=1\quad {\text{и}}\quad \left({\frac {P+2}{N}}\right)=-1} .

На практике необходимо проверить лишь несколько значений P , прежде чем будет найдено одно (5, 8, 9 или 11 подходят примерно для 85% испытаний). [ необходима цитата ]

Чтобы найти начальное значение u 0 из значения P, мы можем использовать последовательность Лукаса (P, 1), как показано в [2], а также на стр. 124 [3] . В последнем поясняется, что когда 3 ∤ k , P = 4 можно использовать, как указано выше, и дальнейший поиск не требуется.

Начальным значением u 0 будет член последовательности Лукаса V k ( P ,1), взятый по модулю  N. Этот процесс выбора занимает очень мало времени по сравнению с основным тестом.

Как работает тест

Тест Лукаса–Лемера–Ризеля является частным случаем проверки простоты порядка группы; мы демонстрируем, что некоторое число является простым, показывая, что некоторая группа имеет тот же порядок, который она имела бы, если бы это число было простым, и мы делаем это, находя элемент этой группы точно такого же порядка.

Для тестов в стиле Люка для числа N мы работаем в мультипликативной группе квадратичного расширения целых чисел по модулю N ; если N — простое число, порядок этой мультипликативной группы равен N 2  − 1, она имеет подгруппу порядка N  + 1, и мы пытаемся найти генератор для этой подгруппы.

Начнем с попытки найти неитеративное выражение для . Следуя модели теста Лукаса–Лемера, положим , и по индукции получим . ты я {\displaystyle u_{i}} ты я = а 2 я + а − 2 я {\displaystyle u_{i}=a^{2^{i}}+a^{-2^{i}}} ты я = ты я − 1 2 − 2 {\displaystyle u_{i}=u_{i-1}^{2}-2}

Итак, мы можем считать, что рассматриваем 2 i -й член последовательности . Если a удовлетворяет квадратному уравнению, это последовательность Люка, и имеет выражение вида . На самом деле, мы рассматриваем k  ⋅ 2 i -й член другой последовательности, но поскольку прореживания (берут каждый k -й член, начиная с нулевого) последовательности Люка сами по себе являются последовательностями Люка, мы можем иметь дело с множителем k , выбрав другую начальную точку. в ( я ) = а я + а − я {\displaystyle v(i)=a^{i}+a^{-i}} в ( я ) = α в ( я − 1 ) + β в ( я − 2 ) {\displaystyle v(i)=\alpha v(i-1)+\beta v(i-2)}

программное обеспечение LLR

LLR — это программа, которая может запускать тесты LLR. Программа была разработана Жаном Пенне. Винсент Пенне модифицировал программу так, чтобы она могла получать тесты через Интернет. [4] Программное обеспечение используется как отдельными искателями простых чисел, так и некоторыми проектами распределенных вычислений, включая Riesel Sieve и PrimeGrid .

Пересмотренная версия LLR2 [5] была развернута в 2020 году. [6] Она генерирует сертификат «доказательства работы», который позволяет проверить вычисления без необходимости полной повторной проверки.

Дальнейшее обновление, PRST [7], использует альтернативную схему сертификата [8] , которая требует больше времени для проверки, но быстрее генерируется для некоторых форм простого кода. [9]

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

Ссылки

  1. ^ Brillhart, John ; Lehmer, Derrick Henry ; Selfridge, John (апрель 1975). "Новые критерии простоты и факторизации 2^m ± 1". Mathematics of Computation . 29 (130): 620–647. doi : 10.1090/S0025-5718-1975-0384673-1 .
  2. ^ ab 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 г.
  3. ^ Ризель, Ганс (1994). Простые числа и компьютерные методы факторизации . Прогресс в математике. Т. 126 (2-е изд.). Биркхойзер. С. 107–121. ISBN 0-8176-3743-5.
  4. ^ Бонат, Карстен (2010-03-12). "LLRnet поддерживает LLR V3.8! (LLRnet2010 V0.73L)". Great Internet Mersenne Prime Search forum . Получено 17 ноября 2021 г.
  5. ^ Атнашев, Павел. "LLR2 GitHub". GitHub . Получено 2023-11-23 .
  6. ^ "LLR2 установлен на всех крупных проектах LLR". Доски объявлений PrimeGrid . 11 сентября 2020 г. Получено 23 ноября 2023 г.
  7. ^ Атнашев, Павел. «ПРСТ GitHub». Гитхаб . Проверено 23 ноября 2023 г.
  8. ^ Ли, Даррен; Галло, Ив (16 сентября 2022 г.). «Эффективная модульная схема доказательства возведения в степень». arXiv : 2209.15623 [cs.CR].
  9. ^ "Проект SR5 перешел на PRST". Доски объявлений PrimeGrid . 19 июля 2023 г. Получено 23 ноября 2023 г.
  • Ризель, Ганс (1969). «Критерий Лукаса для простоты числа N = h ·2 n  − 1». Математика вычислений . 23 (108). Американское математическое общество: 869–875. doi :10.2307/2004975. JSTOR  2004975.
  • Скачать LLR Жана Пенне
  • Math::Prime::Util::GMP — часть модуля Perl ntheory, содержит базовые реализации LLR и тестирования форм Proth, а также некоторые методы доказательства BLS75.
Взято с "https://en.wikipedia.org/w/index.php?title=Lucas–Lehmer–Riesel_test&oldid=1195575248"