Тест Лукаса-Лемера-Ризеля

Тест на определение, является ли число простым

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

Алгоритм

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

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

${\displaystyle u_{i}=u_{i-1}^{2}-2.\,}$

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

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

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

• Если 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. ${\displaystyle u_{0}=(2+{\sqrt {3}})^{k}+(2-{\sqrt {3}})^{k}}$
• В противном случае мы оказываемся в случае, когда k кратно 3, и выбрать правильное значение u ₀ сложнее . Известно, что если k = 3 и n ≡ 0 или 3 (mod 4), то можно взять u ₀ = 5778.

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

${\displaystyle \left({\frac {P-2}{N}}\right)=1\quad {\text{and}}\quad \left({\frac {P+2}{N}}\right)=-1}$.

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

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

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

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

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

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

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

Итак, мы можем считать, что рассматриваем 2 ⁱ -й член последовательности . Если a удовлетворяет квадратному уравнению, это последовательность Люка, и имеет выражение вида . На самом деле, мы рассматриваем k  ⋅ 2 ⁱ -й член другой последовательности, но поскольку прореживания (берут каждый k -й член, начиная с нулевого) последовательности Люка сами по себе являются последовательностями Люка, мы можем иметь дело с множителем k , выбрав другую начальную точку. ${\displaystyle v(i)=a^{i}+a^{-i}}$ ${\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. 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 ⁿ  − 1». Математика вычислений . 23 (108). Американское математическое общество: 869–875. doi :10.2307/2004975. JSTOR  2004975.

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

• Скачать LLR Жана Пенне
• Math::Prime::Util::GMP — часть модуля Perl ntheory, содержит базовые реализации LLR и тестирования форм Proth, а также некоторые методы доказательства BLS75.