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

Чтобы узнать о тесте чисел Мерсенна, см. тест на простоту Лукаса-Лемера . Чтобы узнать о тесте Лукаса-Лемера-Ризеля, см. Тест Лукаса-Лемера-Ризеля . Чтобы узнать о тесте вероятного простого числа Люка, см. псевдопростое число Лукаса .

В вычислительной теории чисел тест Люка — это тест на простоту натурального числа n ; для этого требуется, чтобы простые множители числа n - 1 были уже известны. Это основа сертификата Пратта , который дает краткую проверку того, что n является простым.

Концепции

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм

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

algorithm lucas_primality_test is
    input: n > 2, an odd integer to be tested for primality.
           k, a parameter that determines the accuracy of the test.
    output: prime if n is prime, otherwise composite or possibly composite.

    determine the prime factors of n−1.

    LOOP1: repeat k times:
        pick a randomly in the range [2, n − 1]
            if $a^{n-1}\not \equiv 1{\pmod {n}}$ then
                return composite
            else # $\color {Gray}{a^{n-1}\equiv 1{\pmod {n}}}$
                LOOP2: for all prime factors q of n−1:
                    if $a^{\frac {n-1}{q}}\not \equiv 1{\pmod {n}}$ then
                        if we checked this equality for all prime factors of n−1 then
                            return prime
                        else
                            continue LOOP2
                    else # $\color {Gray}{a^{\frac {n-1}{q}}\equiv 1{\pmod {n}}}$
                        continue LOOP1

    return possibly composite.

См. также

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