Русская Википедия:Тест простоты Люка
В теории чисел тест простоты Люка — это тест простоты натурального числа n; для его работы необходимо знать разложение <math>n-1</math> на множители. Для простого числа n простые множители числа <math>n-1</math> вместе с некоторым основанием a составляют сертификат Пратта, который позволяет подтвердить за полиномиальное время, что число n является простым.
Описание
Пусть n > 1 — натуральное число. Если существует целое a такое, что <math>1<a<n</math> и
- <math>a^{n-1} \equiv 1 \pmod n</math>
и для любого простого делителя q числа <math>n-1</math>
- <math>a^{\frac{n-1}{q}} \not\equiv 1 \pmod n</math>
то n простое.
Если такого числа a не существует, то n — составное число.
Доказательство
Если n простое, то группа вычетов <math>\mathbb{Z}_n</math> циклична, то есть имеет образующую <math>g</math>, порядок которой совпадает с порядком группы <math>|\mathbb{Z}_n^{\times}|=n-1</math>, а значит, для любого простого делителя <math>q</math> числа <math>n-1</math> выполняется сравнение:
- <math>a^{\frac{n-1}{q}} \not\equiv 1 \pmod n.</math>
Если n — составное, то либо <math>\text{НОД}(a,n)>1</math> и тогда <math>a^{n-1} \not\equiv 1 \pmod n</math>, либо <math>a^{n-1} \equiv 1 \pmod n</math>. Если предположить, что для этого a ещё и выполняется <math>a^{\frac{n-1}{q}} \not\equiv 1 \pmod n</math>, то, поскольку <math>\frac{n-1}{q} \mid n-1</math>, получаем, что группа <math>\mathbb{Z}_n^{\times}</math> имеет элемент порядка <math>n-1</math>, значит <math>|\mathbb{Z}_n^{\times}|</math> делит <math>n-1</math>, что противоречит тому, что <math>|\mathbb{Z}_n^{\times}| =\varphi (n)<n-1</math> при составных n.
По закону контрапозиции получаем критерий Люка.
Пример
Например, возьмем n = 71. Тогда <math>n-1=70 = 2 \cdot 5 \cdot 7</math>. Выберем случайно <math>a=17</math>. Вычисляем:
- <math>17^{70} \equiv 1 \pmod {71}.</math>
Проверим сравнения <math>a^{\frac{n-1}{q}} \not\equiv 1 \pmod n</math> для <math>q=2;5;7</math>:
- <math>17^{35} \equiv 70 \not\equiv 1 \pmod {71}</math>
- <math>17^{14} \equiv 25 \not\equiv 1 \pmod {71}</math>
- <math>17^{10} \equiv 1 \equiv 1 \pmod {71}.</math>
К сожалению <math>17^{10} \equiv 1 \equiv 1 \pmod {71}.</math>. Поэтому мы пока не можем утверждать, что 71 простое.
Попробуем другое случайное число a, выберем <math>a=11</math>. Вычисляем:
- <math>11^{70} \equiv 1 \pmod {71}.</math>
Снова проверим сравнения <math>a^{\frac{n-1}{q}} \not\equiv 1 \pmod n</math> для <math>q=2;5;7</math>:
- <math>11^{35} \equiv 70 \not\equiv 1 \pmod {71}</math>
- <math>11^{14} \equiv 54 \not\equiv 1 \pmod {71}</math>
- <math>11^{10} \equiv 32 \not\equiv 1 \pmod {71}.</math>
Таким образом, 71 простое.
Заметим, что для быстрого вычисления степеней по модулю используется алгоритм двоичного возведения в степень со взятием остатка по модулю n после каждого умножения.
Заметим также, что при простом n из обобщенной гипотезы Римана вытекает, что среди первых <math>O(\ln ^2 n)</math> чисел есть хотя бы одна образующая группы <math>\mathbb{Z}_n</math>, поэтому условно можно утверждать, что подобрать основание a можно за полиномиальное время.
Алгоритм
Алгоритм, написанный псевдокодом, следующий:
Ввод: n > 2 - нечетное число, тестируемое на простоту; k - параметр, определяющий точность теста
Вывод: простое, если n простое, в противном случае составное либо возможно составное;
Определяем все простые делители <math>n-1</math>.
Цикл1: Выбираем случайно a из интервала [2, n − 1]
Если <math>a^{n-1} \not\equiv 1 \pmod n</math> вернуть составное
Иначе
Цикл2: Для всех простых <math>q \mid n-1</math>:
Если <math>a^{\frac{n-1}{q}} \not\equiv 1 \pmod n</math>
Если мы не проверили сравнение для всех <math>q</math>
то продолжаем выполнять Цикл2
иначе вернуть простое
Иначе возвращаемся к Циклу1
Вернуть возможно составное.
См. также
Литература
- Василенко О. Н. Теоретико-числовые алгоритмы в криптографии, МЦНМО, 2003
- Трост Э. — Primzahlen / Простые числа — М.: ГИФМЛ, 1959, 135 с
Шаблон:Rq Шаблон:Теоретико-числовые алгоритмы
