Тест на простоту Лукаса - Lucas primality test

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

Концепции

Позволять п быть положительным целым числом. Если существует целое число а, 1 < а < п, так что

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

и для каждого основного фактора q из п − 1

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

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

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

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

пример

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

${ Displaystyle 17 ^ {70} Equiv 1 { pmod {71}}.}$

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

${ displaystyle a ^ {n-1} Equiv 1 { pmod {n}} { text {тогда и только тогда, когда}} { text {ord}} (a) | (n-1).}$

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

${ Displaystyle 17 ^ {35} эквив 70 не эквив 1 { pmod {71}}}$

${ Displaystyle 17 ^ {14} эквив 25 не эквив 1 { pmod {71}}}$

${ Displaystyle 17 ^ {10} Equiv 1 Equiv 1 { pmod {71}}.}$

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

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

${ Displaystyle 11 ^ {70} Equiv 1 { pmod {71}}.}$

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

${ Displaystyle 11 ^ {35} эквив 70 не эквив 1 { pmod {71}}}$

${ Displaystyle 11 ^ {14} Equiv 54 not Equiv 1 { pmod {71}}}$

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

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

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

Алгоритм

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

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

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

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

Заметки