В математике тест Лукаса – Лемера – Ризеля - это критерий простоты для чисел вида N = k ⋅ 2 n - 1, где k <2 n . Тест был разработан Гансом Ризелем и основан на тесте простоты Лукаса – Лемера . Это самый быстрый детерминированный алгоритм, известный для чисел такой формы. [ необходимая цитата ] Для чисел вида N = k ⋅ 2 n + 1 ( числа Прота ) либо применение теоремы Прота ( алгоритм Лас-Вегаса) или одно из детерминированных доказательств, описанных в Brillhart-Lehmer-Selfridge 1975 [1] .
Алгоритм
Алгоритм очень похож на тест Лукаса – Лемера , но с переменной начальной точкой, зависящей от значения k .
Определите последовательность u i для всех i > 0 следующим образом:
Тогда N простое тогда и только тогда, когда оно делит u n −2 .
Нахождение начального значения
Начальное значение u 0 определяется следующим образом.
- Если k = 1: если n нечетное, то мы можем взять u 0 = 4. Если n ≡ 3 (mod 4), тогда мы можем взять u 0 = 3. Обратите внимание, что если n простое, это числа Мерсенна .
- Если k = 3: если n ≡ 0 или 3 (mod 4), то u 0 = 5778.
- Если k ≡ 1 или 5 (mod 6): если 3 не делит N , то берем. См. Ниже, как вычислить это с помощью последовательности Лукаса (4,1).
- В противном случае мы находимся в том случае, когда k кратно 3, и выбрать правильное значение u 0 труднее .
Альтернативный метод нахождения начального значения u 0 приведен в Rödseth 1994. [2] Метод выбора намного проще, чем тот, который использовал Ризель для случая 3 делит k . Сначала найдите значение P, которое удовлетворяет следующим равенствам символов Якоби :
- .
На практике требуется проверить лишь несколько значений P, прежде чем одно будет найдено (5, 8, 9 или 11 работают примерно в 85% испытаний). [ необходима цитата ]
Чтобы найти начальное значение u 0 из значения P, мы можем использовать последовательность Лукаса (P, 1), как показано в [2], а также на странице 124 из. [3] Последний объясняет, что когда 3 ∤ k , можно использовать P = 4, следовательно, более ранний поиск не нужен. Начальное значение U - тогда равно модульный Лукас последовательность V к ( Р , 1) по модулю N . Этот процесс занимает очень мало времени по сравнению с основным тестом.
Как работает тест
Тест Лукаса – Лемера – Ризеля является частным случаем проверки простоты группового порядка; мы демонстрируем, что некоторое число является простым, показывая, что некоторая группа имеет порядок, который он имел бы, если бы это число было простым, и мы делаем это, находя элемент этой группы точно правильного порядка.
Для тестов в стиле Люка для числа N мы работаем в мультипликативной группе квадратичного расширения целых чисел по модулю N ; если N простое число, порядок этой мультипликативной группы равен N 2 - 1, в ней есть подгруппа порядка N + 1, и мы пытаемся найти генератор для этой подгруппы.
Мы начинаем с попытки найти неитеративное выражение для . Следуя модели теста Лукаса – Лемера, положим, и по индукции имеем .
Таким образом , мы можем считать себя , глядя на 2 я го члена последовательности. Если a удовлетворяет квадратному уравнению, это последовательность Люка и имеет выражение вида. На самом деле, мы смотрим на k ⋅ 2 i- й член другой последовательности, но поскольку прореживания (берём каждый k- й член, начиная с нуля) последовательности Люка сами по себе являются последовательностями Люка, мы можем иметь дело с множителем k следующим образом выбор другой отправной точки.
Программное обеспечение LLR
LLR - это программа, которая может запускать тесты LLR. Программа была разработана Жаном Пенне . Винсент Пенне изменил программу, чтобы она могла получать тесты через Интернет. [ необходима цитата ] Программное обеспечение используется как отдельными первичными поисковиками, так и некоторыми проектами распределенных вычислений, включая Riesel Sieve и PrimeGrid .
Смотрите также
Рекомендации
- ^ Бриллхарт, Джон ; Лемер, Деррик Генри ; Селфридж, Джон (апрель 1975 г.). «Новые критерии первичности и факторизации 2 ^ m ± 1» . Математика вычислений . 29 (130): 620–647. DOI : 10.1090 / S0025-5718-1975-0384673-1 .
- ^ а б Рёдсет, Ойстейн Дж. (1994). «Заметка о проверках простоты для N = h · 2 ^ n − 1» (PDF) . BIT Численная математика . 34 (3): 451–454. DOI : 10.1007 / BF01935653 . Архивировано из оригинального (PDF) 6 марта 2016 года.
- ^ Ризель, Ганс (1994). Простые числа и компьютерные методы факторизации . Успехи в математике. 126 (2-е изд.). Birkhäuser. С. 107–121. ISBN 0-8176-3743-5.
- Ризель, Ганс (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.