тест простоты Лукаса

В вычислительной теории чисел тест Лукаса является тестом на простоту натурального числа n ; он требует, чтобы простые множители числа n − 1 были уже известны. ^{[1] [2]} Он является основой сертификата Пратта , который дает краткую проверку того, что n является простым числом.

Концепции

Пусть n — положительное целое число. Если существует целое число a , 1 <  a  <  n , такое, что

${\displaystyle a^{n-1}\ \equiv \ 1{\pmod {n}}\,}$

и для каждого простого множителя q числа n  − 1

${\displaystyle a^{({n-1})/q}\ \not \equiv \ 1{\pmod {n}}\,}$

тогда n — простое число. Если такого числа a не существует, то n — это либо 1, либо 2, либо составное число .

Причина корректности этого утверждения заключается в следующем: если первая эквивалентность верна для a , мы можем вывести, что a и n взаимно просты . Если a также переживает второй шаг, то порядок a в группе ( Z / n Z ) * равен n −1, что означает, что порядок этой группы равен n −1 (потому что порядок каждого элемента группы делит порядок группы), подразумевая, что n является простым числом . И наоборот, если n является простым числом, то существует примитивный корень по модулю n , или генератор группы ( Z / n Z )*. Такой генератор имеет порядок |( Z / n Z )*| =  n −1, и обе эквивалентности будут верны для любого такого примитивного корня.

Обратите внимание, что если существует a <  n  , такое, что первое равенство не выполняется, то a называется свидетелем Ферма составности n .

Пример

Например, возьмем n = 71. Тогда n  − 1 = 70 и простые множители 70 — 2, 5 и 7. Мы случайным образом выбираем a=17  <  n . Теперь мы вычисляем:

${\displaystyle 17^{70}\ \equiv \ 1{\pmod {71}}.}$

Для всех целых чисел a известно, что

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}\ {\text{ if and only if }}{\text{ ord}}(a)|(n-1).}$

Следовательно, мультипликативный порядок 17 (mod 71) не обязательно равен 70, поскольку выше может работать и некоторый множитель 70. Поэтому проверьте 70, деленное на его простые множители:

${\displaystyle 17^{35}\ \equiv \ 70\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 17^{14}\ \equiv \ 25\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 17^{10}\ \equiv \ 1\ \equiv \ 1{\pmod {71}}.}$

К сожалению, мы получаем, что 17 ¹⁰ ≡ 1 (mod 71). Так что мы все еще не знаем, является ли 71 простым числом или нет.

Пробуем еще одно случайное число a , на этот раз выбирая a  = 11. Теперь вычисляем:

${\displaystyle 11^{70}\ \equiv \ 1{\pmod {71}}.}$

Опять же, это не показывает, что мультипликативный порядок 11 (mod 71) равен 70, поскольку может подойти и некоторый множитель 70. Поэтому проверьте 70, деленное на его простые множители:

${\displaystyle 11^{35}\ \equiv \ 70\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 11^{14}\ \equiv \ 54\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 11^{10}\ \equiv \ 32\ \not \equiv \ 1{\pmod {71}}.}$

Таким образом, мультипликативный порядок числа 11 (mod 71) равен 70, и, следовательно, 71 является простым числом.

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

Алгоритм

Алгоритм можно записать на псевдокоде следующим образом:

Алгоритм lucas_primality_test имеет  входные данные : n > 2, нечетное целое число, которое необходимо проверить на простоту. k , параметр, определяющий точность теста. Выходные данные : простое число , если n является простым числом, в противном случае составное число или возможно составное число . определите простые множители числа n −1. LOOP1: повторить  k раз: выбрать a случайным образом в диапазоне [2, n − 1] если  тогда ${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$   вернуть  составной  else  #  ${\displaystyle \color {Gray}{a^{n-1}\equiv 1{\pmod {n}}}}$ LOOP2: для всех простых множителей q числа n −1: если  тогда ${\displaystyle a^{\frac {n-1}{q}}\not \equiv 1{\pmod {n}}}$   если мы проверили это равенство для всех простых множителей числа n −1 тогда  вернуть  простой  else  продолжить LOOP2 else  # продолжить LOOP1  ${\displaystyle \color {Gray}{a^{\frac {n-1}{q}}\equiv 1{\pmod {n}}}}$  возврат  возможно составной .

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

• Эдуард Люка , в честь которого назван этот тест
• Малая теорема Ферма
• Тест Поклингтона на простоту — улучшенная версия этого теста, которая требует только частичной факторизации n  − 1
• Сертификат первичности

Примечания

1. Крэндалл, Ричард; Померанс, Карл (2005). Простые числа: вычислительная перспектива (2-е изд.). Springer. стр. 173. ISBN 0-387-25282-7.
2. Кржижек, Михал; Лука, Флориан; Сомер, Лоуренс (2001). 17 лекций по числам Ферма: от теории чисел к геометрии . Книги по математике CMS. Т. 9. Канадское математическое общество/Springer. стр. 41. ISBN 0-387-95332-9.