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

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

Концепции [ править ]

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

${\ Displaystyle а ^ {п-1} \ \ эквив \ 1 {\ pmod {п}} \,}$

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

${\ Displaystyle а ^ {({п-1}) / д} \ \ не \ эквив \ 1 {\ pmod {п}} \,}$

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

Причина в правильности этого утверждения заключается в следующем: если первая эквивалентность имеет место для , мы можем сделать вывод , что и п являются взаимно простыми . Если также выживает второй шаг, затем порядок из в группе ( Z / п Z ) * равно п -1, что означает , что порядок этой группы является п -1 (потому что порядок каждого элемента группу делит порядок группы), подразумевая , что п является простым . Наоборот, если 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 {тогда и только тогда, когда}} {\ text {ord}} (a) | (n-1).}$

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

${\ Displaystyle 17 ^ {35} \ \ Equiv \ 70 \ \ not \ Equiv \ 1 {\ pmod {71}}}$

${\ Displaystyle 17 ^ {14} \ \ эквив \ 25 \ не \ эквив \ 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} \ \ эквив \ 70 \ не \ эквив \ 1 {\ pmod {71}}}$

${\ Displaystyle 11 ^ {14} \ \ эквив \ 54 \ не \ эквив \ 1 {\ pmod {71}}}$

${\ Displaystyle 11 ^ {10} \ \ эквив \ 32 \ не \ эквив \ 1 {\ pmod {71}}.}$

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

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

Алгоритм [ править ]

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

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

См. Также [ править ]

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

Заметки [ править ]