Теорема Прота

Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!

История

Франсуа Прот (1852–1879) был фермером-самоучкой, который жил во французской деревне Во-деван-Дамлу недалеко от Вердена. Рассматриваемая здесь теорема, является одним из четырех полученных им результатов, которые можно использовать для проверки простоты чисел. Она была опубликована во французском научном журнале «Comptes rendus de l'Académie des Sciences» (рис. 1) в 1878 году. Вероятно, у Прота были доказательства своих результатов, однако он их не представил.

Определение

Теорема Прота – это детерминированный тест на простоту с полиномиальным временем. Иначе говоря, он даёт гарантированно точный ответ, простое ли исследуемое число или нет, и время его работы ограничено сверху многочленом от размера входа алгоритма. Несмотря на это, рассматриваемый тест не получил широкого практического применения вследствие сложности алгоритма его реализации и ввиду того, что он работает только с определённой группой чисел – числами Прота.

Числа Прота

Числа Прота – это натуральные числа вида $k\cdot2^n+1$ , где является нечётным положительным целым числом и – положительным целым числом. Более того, необходимо выполнение условия k<2^n , без которого числами Прота были бы все нечётные целые числа больше единицы. Например, число 448 будет являться числом Прота, так как оно может быть представлено в виде $7\cdot2^6+1$ , причём 2^6>7 .

Первые числа Прота составляют следующую последовательность: 3, 5, 9,13,17, 25, 33… Эта последовательность представлена в онлайн-энциклопедия целочисленных последовательностей под индексом A080075.

Однако, гораздо больший интерес представляют простые числа Прота, составляющие следующую последовательность: 3, 5, 13, 17, 41, 97, 113… Её также можно найти в онлайн-энциклопедии под индексом A080076.

Наибольшим известным простым числом Прота является число $10223\cdot2^{31172165}+1$ , которое состоит из 9,383,761 десятичной цифры. Примечательно, что оно также является крупнейшим известным простым числом, не являющимся числом Мерсена вида 2^n-1 . Это число было обнаружено 31 октября 2016 года Петером Сабольчем в проекте добровольных вычислений Seventeen or Bust по отысканию простых чисел вида $k\cdot2^n+1$ .

Стоит также отметить, что числа Прота являются обобщением для некоторых других числовых групп. Например, числа Каллена ( $n\cdot2^n+1$ ) являются частным случаем чисел Прота при k=n , а числа Ферма вида ( $2^{2^n}+1$ ) – при k=1 .

Формулировка теоремы

Если – число Прота, то оно является простым тогда и только тогда, когда для некоторого квадратичного невычета выполняется следующее сравнение:

$a^{\frac{p-1}{2}}\equiv-1 ~(\text{mod}~p)$

Здесь требуется пояснение. Числоназывается квадратичным невычетом по модулю , если сравнение $x^2\equiv a ~(\text{mod}~m)$ не имеет решения. И наоборот, если такое сравнение разрешимо, то число называется квадратичным вычетом по модулю .

Критерий Эйлера

Для определения, является ли данное целое число квадратичным вычетом по модулю простого числа, часто используется критерий Эйлера. У него существует несколько формулировок, однако в данной работе мы рассмотрим только одну.

Пусть m>2 – простое. Число , взаимно простое с будет являться квадратичным вычетом по модулю тогда и только тогда, когда $a^{(p-1)/2}\equiv1 ~(\text{mod}~p)$ и будет являться квадратичным невычетом по модулю тогда и только тогда, когда $a^{(p-1)/2}\equiv-1 ~(\text{mod}~p)$ .

Например, число – квадратичный невычет по простому модулю , так как выполняется следующее сравнение: $2^5=32\equiv-1~(\text{mod}~11)$ . А число – квадратичный вычет по модулю так как $3^5=243\equiv1~(\text{mod}~11)$ .

Этот критерий удобно использовать для доказательства рассматриваемой нами теоремы Прота. Помимо этого, не лишим будет рассмотреть критерий Поклингтона на простоту чисел. Он является обобщенным случаем теоремы Прота, поэтому его также используют для доказательства.

Критерий Поклингтона

Пусть – натуральное число и пусть n-1 имеет простой делитель , причем $q>\sqrt{n}-1$ . Если найдётся такое целое число , для которого выполняются условия $a^{n-1}\equiv1~(\text{mod}~n)$ и числа и $a^{(n-1)/q}-1$ взаимно просты, то – простое число.

Рассмотрим пример. Пусть n=7 . Докажем, что это простое число. Для начала найдём простой делитель числа n-1 , то есть . Их несколько, поэтому можем выбрать любой. Пусть q=3 . Условие $3>\sqrt{7}-1\approx1,65$ выполнено. Для подтверждения простоты числа необходимо найти такое число , для которого выполняются оба требования критерия. Пусть a=2 , тогда $2^{6}\equiv1~(\text{mod}~7)$ и числа и $2^{(7-1)/3}-1=3$ взаимно просты. Следовательно, число является простым по критерию Поклингтона.

Изначально этот критерий был сформулирован для таких чисел, которые имеют простой делитель кратности . Однако, он легко обобщается и для тех случаев, когда кратность равна k>1 . Нужно лишь слегка изменить одно из условий: $q^k>\sqrt{n}-1$ .

Например, такому случаю соответствует число n=17 . Единственным простым делителем числа n-1=16 будет q=2 . Легко заметить, что условие $2>\sqrt{17}-1\approx3,12$ не выполняется. Но q=2 является делителем числа n-1=16 кратности k=4 . Поэтому соответствующее условие будет выглядеть следующим образом: $2^4>\sqrt{17}-1\approx3,12$ . Теперь неравенство, очевидно, выполняется, и мы можем использовать критерий Поклингтона, который даст закономерный результат: число n=17 – простое.

Доказательство теоремы Прота

Доказательство теоремы состоит из двух частей. Для начала докажем, что для простого числа Прота имеет место сравнение $a^{(p-1)/2}\equiv-1 ~(\text{mod}~p)$ .

Пусть число – простое. Тогда по критерию Эйлера для любого квадратичного невычета выполняется сравнение $a^{(p-1)/2}\equiv-1 ~(\text{mod}~p)$ . Доказано.

Теперь необходимо показать, что число Прота будет простым, если $a^{(p-1)/2}\equiv-1 ~(\text{mod}~p)$ .

Пусть сравнение $a^{(p-1)/2}\equiv-1 ~(\text{mod}~p)$ разрешимо для некоторого квадратичного невычета .

Воспользуемся критерием Поклингтона для n=p=2^k+1 . В этом случае q=2 является единственным простым делителем числа n-1 .

Далее проверяем, выполняются ли условия критерия:

$a^{n-1}=\left(a^{(n-1)/2}\right)^2\equiv1 ~(\text{mod}~n)$ – выполнено
Числа и $a^{(n-1)/q}-1$ взаимно просты – выполнено

Также выполняется условие $2^k>\sqrt{n}-1$ . Тогда по критерию Поклингтона число n=p является простым. Что и требовалось доказать.

Тестирование чисел Прота на простоту

Теорему Прота можно использовать для тестирования простоты чисел Прота. Как уже упоминалось выше, эта теорема даёт гарантированно верный ответ на вопрос, простое ли исследуемое число или нет. Однако, на практике гораздо удобнее применять вероятностные тесты, основанные на теореме, поскольку они значительно проще и работают на несколько порядков быстрее. Рассмотрим один из таких.

Пусть необходимо проверить, является ли число простым. Для этого мы случайным образом выбираем целое число , такое что $a\not\equiv1~(\text{mod}~N)$ . Вычислим значение выражения $b=a^{(n-1)/2}$ и найдём его остаток от деления на число .

Возможны следующие исходы:

$b\equiv-1~(\text{mod}~N)$ . В этом случае мы можем утверждать, что число – простое по теореме Прота.
$b\not\equiv\pm1~(\text{mod}~N)$ и $b^2\equiv1~(\text{mod}~N)$ . При выполнении этих условий, оказывается, что число – составное, так как НОД( $b\pm1,N$ ) будут нетривиальными делителями числа.
$b^2\not\equiv1~(\text{mod}~N)$ . Здесь – составное по малой теореме Ферма.
$b\equiv1~(\text{mod}~N)$ . В этом случае результат неизвестен.

Последний исход как раз и является причиной того, что тест вероятностный. Даже если число заведомо простое, тест подтвердит это за одну итерацию только с вероятностью 1/2 .

Дело в том, что для гарантированно верного ответа необходимо соблюдение всех условий теоремы Прота. Иначе говоря, число должно являться квадратичным невычетом по модулю . Известно, что среди ненулевых чисел 1,2,...,N-1 для простого модуля существует ровно (N-1)/2 квадратичных вычетов и столько же квадратичных невычетов. По этой причине при произвольном выборе числа , оно окажется невычетом с вероятностью 1/2 . Только в этом случае мы сможем утверждать, что число – простое.

Рассмотрим пример работы данного алгоритма. Пусть необходимо проверить на простоту число N=17 . Выберем случайным образом число . Например, a=2 , тогда b=256 . Находим остаток от деления числа на число . Получаем, что $256\equiv1~(\text{mod}~17)$ . Это соответствует неопределённому исходу. Следовательно, нам необходимо выбрать другое число .

Пусть теперь a=3 . Тогда b=6561 и $6561\equiv-1~(\text{mod}~17)$ . Таким образом, мы получили, что число N=17 является простым по теореме Прота.

Поскольку мы заранее знали, что число – простое, нам не составило труда подобрать такое , которое даст достоверный результат. Однако, при проверке произвольных чисел поиск невычетов занимает слишком много времени. Поэтому данный алгоритм гораздо чаще используется для «отсеивания» составных чисел. Рассмотрим пример.

Пусть дано число N=9 и необходимо проверить, является ли оно простым. Выберем число равным . Тогда b=16 . Остаток от деления числа на число N=9 равен . Иначе говоря, $16\equiv7\neq\pm1~(\text{mod}~9)$ . Это соответствует второму или третьему исходу. В любом случае получается, что число N=9 является составным.

Представленный тест называется алгоритмом Лас-Вегаса. Он никогда не возвращает ложноположительный результат, но может возвращать ложноотрицательный результат. Другими словами, он никогда не объявляет составное число как «возможно простое», но может объявлять простое число как «возможно составное». Данный алгоритм работает за конечное, но не определенное время, которое может меняться случайным образом. Можно указать только вероятность получения результата за заданное время.

В 2008 году был разработан детерминированный алгоритм, который работает за время, ограниченного величиной $O((k\log k+\log N)(\log N)^2)$ . Этот алгоритм был взят Ивом Галло за основу при написании известной в математических кругах программы "Proth.exe", позволяющей проверять числа Прота на простоту.

Обобщенная теорема Прота

Рассмотрим теперь обобщенную теорему Прота.

Пусть число представимо в виде N=r^et+1 , где – некоторое простое число, а и – целые, для которых выполняется неравенство $e,t\geq1$ . Пусть также r^e>t . Тогда, если $a^{N-1}\equiv1~(\text{mod}~N)$ и $a^{(N-1)/r}\not\equiv1~(\text{mod}~N)$ для некоторого целого числа , то – простое.

Рассмотрим пример. Предположим, необходимо проверить на простоту число N=17 . Оно представимо в виде $N=17=2^4\cdot1+1$ . Тогда r=2,~e=4,~t=1 . Легко видеть, что требуемые в условии теоремы неравенства выполнены. Далее нам необходимо проверить критерий простоты рассматриваемого числа для некоторого целого . Пусть a=3 . Получаем следующее:

$3^{16}\equiv1~(\text{mod}~17)$ – верно
$3^{8}\not\equiv1~(\text{mod}~17)$ – верно

Следовательно, как и ожидалось, число N=17 является простым.

Конечно, обобщенная теорема Прота применима для большего количества числовых групп, однако подбор необходимых переменных требует слишком много времени. Поэтому на практике гораздо чаще используется классическая теорема.

Источник: https://habr.com/ru/post/545208/

Вернуться к списку

Интересные статьи

Выгрузка пользователей из 1C ЗУП в Битрикс24 или правдивая история о том как настроить интеграцию 1С-Битрикс24 c 1С ЗУП

Выгрузка пользователей из 1C ЗУП в Битрикс24 или правдивая история о том как настроить интеграцию 1С-Битрикс24 с ЗУП без 1С-ника В жизни так бывает, причём бывает чаще чем хотелось б...

Описание сервиса маркетплейс 1С-Битрикс. Как начать разрабатывать приложения для marketplace?

Маркетплейс – это сервис от 1С-Битрикс, который позволяет разработчикам делиться своими решениями с широкой аудиторией, состоящей из клиентов и других разработчиков.

Фоновая загрузка изображений vue lazyload на 1С-Битриксе

VUE.JS - это javascript фрэймворк, с версии 18.5 его добавили в ядро битрикса, поэтому можно его использовать из коробки.

А-Б-тестирование в 1С-Битрикс, как способ провести время

У некоторых бизнес-тренеров в области е-коммерса и консультантов по увеличению интернет-продаж на многие вопросы часто можно слышать универсальную отмазку — «надо тестировать» или другую (чтобы не...

Обзор CRM систем: amoCRM, retailCRM, Битрикс24

Сравнивать CRM системы – дело неблагодарное. Очень уж сильно они отличаются в целях создания, реализации, в деталях.