Тест простоты Люка


Тест простоты Люка

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

Содержание

Описание

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

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

и для любого простого делителя q числа n-1

a^{\frac{n-1}{q}} \not\equiv 1 \pmod n

то n простое.

Если такого числа a не существует, то nсоставное число.

Доказательство

Если n простое, то группа вычетов \mathbb{Z}_n циклична, то есть имеет образующую g, порядок которой совпадает с порядком группы |\mathbb{Z}_n^{\times}|=n-1, а значит, для любого простого делителя q числа n-1 выполняется сравнение:

a^{\frac{n-1}{q}} \not\equiv 1 \pmod n.

Если n - составное, то либо \text{НОД}(a,n)>1 и тогда a^{n-1} \not\equiv 1 \pmod n, либо a^{n-1} \equiv 1 \pmod n. Если предположить, что для этого a еще и выполняется a^{\frac{n-1}{q}} \not\equiv 1 \pmod n, то, поскольку \frac{n-1}{q} \mid n-1, мы получаем, что группа \mathbb{Z}_n^{\times} имеет элемент порядка n-1, значит |\mathbb{Z}_n^{\times}| делит n-1, что противоречит тому, что |\mathbb{Z}_n^{\times}| =\varphi (n)<n-1 при составных n.

Теперь, по закону контрапозиции, получаем критерий Люка.

Пример

Например, возьмем n = 71. Тогда n-1=70 = 2 \cdot 5 \cdot 7. Выберем случайно a=17. Вычисляем:

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

Проверим сравнения a^{\frac{n-1}{q}} \not\equiv 1 \pmod n для q=2;5;7~:

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^{10} \equiv 1 \equiv 1 \pmod {71}.. Поэтому мы пока не можем утверждать, что 71 простое.

Попробуем другое случайное число a, выберем a=11. Вычисляем:

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

Снова проверим сравнения a^{\frac{n-1}{q}} \not\equiv 1 \pmod n для q=2;5;7~:

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}.

Таким образом, 71 простое.

Заметим, что для быстрого вычисления степеней по модулю используется алгоритм двоичного возведения в степень со взятием остатка по модулю n после каждого умножения.

Заметим также, что при простом n из обобщенной гипотезы Римана вытекает, что среди первых O(\ln ^2 n)~ чисел есть хотя бы одна образующая группы \mathbb{Z}_n, поэтому условно можно утверждать, что подобрать основание a можно за полиномиальное время.

Алгоритм

Алгоритм, написанный псевдокодом следующий:

Ввод: n > 2 - нечетное число, тестируемое на простоту; k - параметр, определяющий точность теста
Вывод: простое, если n простое, в противном случае составное либо возможно составное;
Определяем все простые делители n-1.
Цикл1: Выбираем случайно a из интервала [2, n − 1]
      Если a^{n-1} \not\equiv 1 \pmod n вернуть составное
      Иначе 
         Цикл2: Для всех простых q \mid n-1:
            Если a^{\frac{n-1}{q}} \not\equiv 1 \pmod n
               Если мы не проверили сравнение для всех q
                  то продолжаем выполнять Цикл2
               иначе вернуть простое
            Иначе возвращаемся к Циклу1
Вернуть возможно составное.

См. также

Литература

  • Василенко О. Н. Теоретико-числовые алгоритмы в криптографии, МЦНМО, 2003
  • Трост Простые числа



Wikimedia Foundation. 2010.

Смотреть что такое "Тест простоты Люка" в других словарях:

  • Тест простоты — Тест простоты  алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты. Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только… …   Википедия

  • Вероятностный тест простоты — Тест простоты  алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты. Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только в… …   Википедия

  • Тест Люка — Тест Люка  Лемера  эффективный тест простоты для чисел Мерсенна. Благодаря этому тесту самые большие простые числа всегда были числами Мерсенна даже задолго до появления компьютеров.[1] Содержание 1 История 2 Тест 3 …   Википедия

  • Тест Люка — Лемера — эффективный тест простоты для чисел Мерсенна. Этот тест был предложен Люка в 1878 году и в 1930 году усовершенствован Лемером (Lehmer). Тест Люка Лемера базируется на том наблюдении, что простота числа Мерсенна Mp = 2p 1 влечёт простоту …   Википедия

  • Тест — (от слова англ. test)  «испытание», «проверка» это метод изучения глубинных процессов деятельности человека, посредством его высказываний или оценок факторов функционирования системы управления Содержание 1 Программирование 2 Математика …   Википедия

  • Тест Ферма — Тест простоты Ферма в теории чисел  это тест простоты натурального числа n, основанный на малой теореме Ферма. Содержание Если n  простое число, то оно удовлетворяет сравнению для любого a, где n не делит a. Выполнение сравнения… …   Википедия

  • Тест Пепина — тест простоты для чисел Ферма. Описание Псевдокод ОТ ДО ВЫП ЕСЛИ ТО ВОЗВРАТ « …   Википедия

  • Тест Миллера (теория чисел) — У этого термина существуют и другие значения, см. Тест Миллера. Не следует путать с «Тестом Миллера Рабина»  вероятностным полиномиальным тестом простоты. Тест Миллера  детерминированный полиномиальный тест простоты. В 1976 году Миллер… …   Википедия

  • Тест Агравала — В информатике тест Агравала  Каяла  Саксены (или тест AKS)  это полиномиальный детерминированный тест простоты чисел, предложенный индийскими учёным Маниндрой Агравалом (англ.) и его двумя студентами Нираджем Каялом (англ …   Википедия

  • Тест (значения) — Может, вы искали ?Тест (от слова en. test) испытание, проверка, анализ. Программирование * Тестирование программного обеспечения * Тест Тьюринга * Бета тестирование Тесты в биологических и биохимических исследованиях * Тест на ВИЧ *… …   Википедия