Тест Лукаса на простоту

В вычислительной теории чисел тест Люка — это тест на простоту натурального числа 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}}.}$

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

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

Следовательно, мультипликативный порядок 17 (по модулю 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 (по модулю 71). Итак, мы до сих пор не знаем, является ли 71 простым или нет.

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

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

Опять же, это не означает, что мультипликативный порядок 11 (по модулю 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 (по модулю 71) равен 70, и, следовательно, 71 является простым числом.

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

Алгоритм

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

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

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

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

Примечания

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