Классические и квантовые вычисления

Вероятностные алгоритмы и класс BPP. Проверка простоты числа

Разбить на страницы
Показывать лекцию целиком

В вероятностных МТ (ВМТ), как и в недетерминированных, имеются состояния, из которых возможен переход в несколько (больше одного) состояний. Отличие состоит в том, что состояние, куда ВМТ делает переход, определяется результатом некоторого случайного процесса ("подбрасывания монеты"). Нужно оговорить, какие монеты допускаются. Например, если взять монету, вероятность выпадения герба для которой равна невычислимому числу, то возможности ВМТ, использующей подбрасывание такой монеты, будут больше, чем хотелось бы; она сможет вычислить и некоторые неразрешимые предикаты.

Обычно считают, что вероятности выпадения одинаковы для обеих сторон монеты, а результат подбрасывания отождествляется с числом 0 или 1.

Хотя для ВМТ нельзя сказать, какой в точности ответ она выдаст, можно определить вероятность того или иного ответа.

Определение 3.1. Предикат $$L$$ принадлежит классу BPP, если существуют такие ВМТ $$M$$ и полином $$p(n)$$, что машина $$M$$ заведомо остановится за время, не превосходящее $$p(|x|)$$, причем

$$L(x)=1$$ $$\Longrightarrow$$ $$M$$ с вероятностью большей $$2/3$$ дает ответ "да";

$$L(x)=0$$ $$\Longrightarrow$$ $$M$$ с вероятностью большей $$2/3$$ дает ответ "нет".

Если в этом определении заменить число $$2/3$$ на любое фиксированное число, большее $$1/2$$, класс BPP не изменится. Есть простой способ добиться вероятности, сколь угодно близкой к 1. Возьмем несколько одинаковых машин, запустим их все, а окончательным результатом будем считать мнение большинства. Если вероятность правильного ответа для каждого экземпляра машины равна $$c>1/2$$, то можно доказать, что вероятность правильного ответа после голосования $$n$$ машин не меньше $$1-\lambda^n$$, где $$\lambda=2\sqrt{c(1-c)}<1$$.

Замечание 3.1. Представить физическую реализацию НМТ очень трудно (вспомним, что нам придется поместить в нее всезнайку Мерлина). А вероятностные машины вполне могут мыслиться как реальные устройства. Поэтому предикаты из класса BPP вполне можно считать реально вычислимыми.

Класс BPP можно определить и с помощью предикатов от двух переменных, как это было сделано для класса NP.

Определение 3.2. Предикат $$L$$ принадлежит классу BPP, если существуют такие полином $$q(\cdot)$$ и предикат $$R(\cdot,\cdot)\in\P$$, что

$$L(x)=1$$ $$\Longrightarrow$$ доля слов $$r$$ длины $$q(|x|)$$, для которых выполнено $$R(x,r)$$, больше $$2/3$$ ;

$$L(x)=0$$ $$\Longrightarrow$$ доля слов $$r$$ длины $$q(|x|)$$, для которых выполнено $$R(x,r)$$, меньше $$1/3$$.

Теорема 3.1. Определения 3.1 и 3.2 эквивалентны.

Доказательство Опр. 3.1 $$\Longrightarrow$$ Полагаем $$q(n)=p(n)$$ (количество подбрасываний монеты не превосходит общего числа действий). Определим предикат $$R(x,r)=$$ "машина $$M$$ на входе $$x$$ дает ответ "да" при указанной в $$r$$ последовательности результатов подбрасываний монеты". Этот предикат по очевидным причинам удовлетворяет определению 3.2.

Опр. 3.2 $$\Longrightarrow$$ опр. 3.1. Случайно выбираем слово $$r$$ длины $$q(|x|)$$ и подставляем в предикат, затем вычисляем значение предиката. Такая ВМТ удовлетворяет определению 3.1.

Определение 3.2 допускает следующее наглядное толкование. Отметим на плоскости $$(x,y)$$ точки из множества $$\{(x,y):R(x,y)\wedge(|y|=q(|x|))\}$$. Для $$x=x_0$$ рассмотрим сечение $$\{(x,y):R(x,y)\double\wedge (|y|=q(|x|))\wedge(x=x_0)\}$$ этого множества. Предикат $$R(\cdot,\cdot)$$, участвующий в определении 3.2, обладает таким странным свойством, что мера этого сечения при любом $$x_0$$ либо больше $$2/3$$, либо меньше $$1/3$$. Это разделяет значения $$x$$ на две категории: одна соответствует истинности предиката $$L$$, другая — ложности.

(рис 3.1)

Классический пример задачи из BPP представляет проверка простоты числа: дано число $$n$$, требуется определить, простое ли оно. Для этой задачи существует вероятностный алгоритм, работающий за полиномиальное время; он будет сейчас описан.

Необходимые сведения из теории чисел.

Подробное изложение элементарной теории чисел содержится в книге [2]. Мы лишь напомним две теоремы, которые будут важны при анализе работы алгоритма проверки простоты числа.

Малая теорема Ферма. Если $$n$$ — простое и $$n\nmid a$$, то $$a^{n-1}\equiv1\pmod n$$.

Китайская теорема об остатках. Пусть $$n=uv$$ — разложение числа на взаимно простые множители. Тогда $$\ZZ/n\ZZ=\ZZ/u\ZZ\times\ZZ/v\ZZ$$.

Другими словами, существует взаимно однозначное соответствие между остатками от деления на $$n$$ и парами остатков от деления на $$u$$ и на $$v$$. {И это соответствие уважает операции сложения и умножения.)

Из малой теоремы Ферма следует, что $$a^{n-1}\not\equiv1\hskip-1pt\pmod n$$ позволяет утверждать, что $$n$$ — составное (говорят, что $$a$$ является свидетелем непростоты числа $$n$$ ). Это свидетельство косвенное — явного разложения $$n$$ на множители мы не получаем — и сильное: часто достаточно проверки при $$a=2$$!

Однако проверки малой теоремы Ферма даже при всех $$a$$ может оказаться недостаточно. Алгоритм проверки будет использовать свидетелей еще одного типа: если $$b^2\equiv1\pmod n$$, а $$b\not\equiv\pm1\pmod n$$, то $$n$$ — составное; $$n$$ и $$b-1$$ имеют общий делитель, больший 1. Поэтому свидетели такого вида (вообще говоря, гораздо более редко появляющиеся) позволяют сразу же указать разложение $$n$$ (против простоты которого они свидетельствуют) на два множителя за полиномиальное время (наибольший общий делитель $$(x,y)$$ двух чисел $$x$$ и $$y$$ можно найти за полиномиальное время, см. ниже).

Необходимые сведения из алгоритмической теории чисел.

Арифметические операции над числами можно выполнять за полиномиальное время от длины их записи (число $$n$$ записывается $$\lceil\log n\rceil\double=O(\log n)$$ знаками). Например, схема умножения чисел $$n$$, $$m$$ столбиком имеет размер $$O(\log n\log m)$$, растущий квадратично от длины входа. Хотя квадрат от длины входа уже достаточно мал, чтобы быть полиномиальным, заметим, что для умножения $$n$$ -значных чисел есть и более экономные схемы размера $$O(n\log n\log\log n)$$, см.[1, р.7.5] или [7, т. 2, р.4.3.3].

В модулярной арифметике (арифметике остатков по модулю заданного числа $$q$$ ) можно вычислить $$a^n$$ по модулю $$q$$ схемой полиномиального размера от длины входа $$(a,n,q)$$ (в обычной арифметике даже результат возведения в степень может иметь экспоненциальный размер). Для этого нужно вычислить остатки от степеней $$a^{2^k}$$ последовательным возведением в квадрат и затем перемножить те из полученных чисел, которым соответствуют 1 в двоичной записи числа $$n$$.

Наибольший общий делитель двух чисел можно найти, пользуясь алгоритмом Евклида, использующим рекурсивно равенство $$(x,y)\double=(y,x\bmod y)$$. Если делить большее число на меньшее, то за каждые два шага длина записи меньшего числа уменьшается на константу.

Существует также алгоритм проверки того, что из числа извлекается нацело корень $$k$$ -й степени. Это можно сделать, найдя достаточно точно приближенное значение корня и возведя ближайшее к нему целое число в $$k$$ -ю степень. Найти приближенное значение $$\sqrt[k\mkern3mu]{x}$$ можно с помощью рекуррентной последовательности$$a_{n+1}=\frac{1}{k}\left((k-1)a_n+\frac{x}{a_n^{k-1}}\right),$$ если выбрать подходящее значение $$a_0$$. Детали этого (полиномиального) алгоритма оставляются читателю для самостоятельного обдумывания.

Заметим, что все схемы, о которых шла речь выше, могут быть построены МТ за полиномиальное время. Так что все перечисленные задачи принадлежат классу P.

Алгоритм проверки простоты.

Вход: число $$n$$.

Шаг 1. Проверяем четность $$n$$. Если $$n=2$$, то ответ " $$n$$ — простое", если $$n$$ — четное и больше 2, то ответ " $$n$$ — составное", в противном случае переходим к шагу 2.

Шаг 2. Проверяем, извлекается ли из $$n$$ нацело корень $$k$$ -й степени при $$k=2,\dots,\lfloor\log_2n\rfloor$$. Если извлекается, то ответ " $$n$$ — составное", иначе переходим к шагу 3.

Шаг 3. Записываем $$n-1$$ в виде $$2^k\cdot l$$, где $$k>0$$, а $$l$$ — нечетное.

Шаг 4. Выбираем случайное $$a$$ среди чисел от $$1$$ до $$n$$.

Шаг 5. Вычисляем $$a^l,\ a^{2l},\ \dots,\ a^{n-1}$$ по модулю $$n$$.

Проверка 1. Если $$a^{n-1}\not\equiv1\pmod n$$, то ответ " $$n$$ — составное".

Проверка 2. Если найдено такое $$j$$, для которого $$a^{2^jl}\not\equiv\pm1\pmod n$$, а $$a^{2^{j+1}l}\equiv1\pmod n$$, то ответ " $$n$$ — составное".

В противном случае ответ " $$n$$ — простое".

Анализ алгоритма.

Теорема 3.2. Если $$n$$ — простое, то описанный выше алгоритм всегда (с вероятностью 1) выдает ответ " $$n$$ — простое".

Если $$n$$ — составное, то ответ " $$n$$ — составное" будет получен с вероятностью $$\geq1/2$$.

Замечание 3.2. Чтобы получить полиномиальный вероятностный алгоритм проверки простоты числа в смысле определения 3.1, нужно дважды применить приведенный алгоритм. Тогда вероятность ошибки станет меньше $$1/4$$.

Доказательство (теоремы 3.2). Из сказанного выше следует, что в доказательстве нуждается только второе утверждение.

Пусть $$n=uv\equiv1\pmod2$$, где $$(u,v)=1$$ (если такого представления нет, то на шаге 2 будет обнаружена непростота). Если $$(a,n)>1$$, то проверка 1 для такого $$a$$ заведомо обнаружит, что $$n$$ — составное. Так что достаточно доказать, что не меньше половины тех $$a$$, которые взаимно просты с $$n$$, обнаруживают непростоту числа.

Обозначим группу $$(\ZZ/u\ZZ)^*$$ через $$U$$, группу $$(\ZZ/v\ZZ)^*$$ — через $$V$$. Из китайской теоремы об остатках следует, что группа $$(\ZZ/n\ZZ)^*$$ изоморфна $$U\times V$$ (изоморфизм задается естественным образом — вычислением остатков по модулю $$u$$ и по модулю $$v$$ ).

Рассмотрим множества $$U^k=\{x^k: x\in U\}$$, $$V^k=\{x^k: x\in V\}$$. Это подгруппы в $$U$$ и $$V$$ соответственно (произведение $$k$$ -х степеней есть $$k$$ -я степень, обратный к $$k$$ -й степени есть $$k$$ -я степень). Так что $$|U|/|U^k|$$ — целое число. Более того, отображение $$x\mapsto x^k$$ является гомоморфизмом групп, поэтому число прообразов при этом отображении одинаково для всех элементов $$U^k$$.

Очевидно, что $$U^{2l}\subseteq U^l$$ (степеней квадратов не больше, чем всех степеней). Поэтому получаем пару невозрастающих цепочек множеств$$U^l\supseteq U^{2l}\supseteq \ldots \supseteq U^{n-1}\supseteq\{1\},\qquad V^l\supseteq V^{2l}\supseteq \ldots \supseteq V^{n-1}\supseteq\{1\}.$$ Дальнейшее рассуждение разбивается на анализ нескольких случаев.

  • Пусть $$U^{n-1}\ne\{1\}$$ или $$V^{n-1}\ne\{1\}$$.

    Чтобы пройти проверку 1 в алгоритме, нужно после возведения в $$(n-1)$$ -ю степень получить пару остатков $$(1,1)$$. Поскольку прообразов каждого числа из $$U^{n-1}\ne\{1\}$$ одинаковое количество, вероятность получения пары $$(1,1)$$ не выше $$1/2$$.

  • Пусть $$U^{n-1}=V^{n-1}=\{1\}$$.

    Поскольку $$l$$ — нечетное, $$-1\in U^{l}\cap V^l$$, т.е. найдется такое $$t=2^s$$, $$0\le s<k$$, что $$U^{2t}\double=V^{2t}=\{1\}$$, а $$U^t\ne\{1\}$$ или $$V^t\ne\{1\}$$.

    Будем доказывать, что с вероятностью не меньше $$1/2$$ в этом месте проверка 2 алгоритма обнаружит, что $$n$$ — составное. В данном случае $$a^{2t}\equiv1 \pmod n$$, так что нужно понять, с какой вероятностью $$a^t$$ не равно $$\pm1$$. Рассмотрим два случая.

  • Одно из множеств $$U^t$$, $$V^t$$ равно $$\{1\}$$. Пусть, например, $$U^t\double=\{1\}$$. В этом случае можно утверждать, что $$a^t\not\equiv-1\pmod n$$ (остатку $$-1$$ при делении на $$n$$ соответствует пара остатков $$(-1,-1)$$ при делении на $$u,v$$ ).

    Можно рассуждать так же, как и в случае 1. С вероятностью не меньше $$1/2$$ получим пару остатков $$(1, \alpha)$$, $$\alpha\ne1$$.

  • Оба множества $$U^t, V^t$$ содержат по крайней мере два элемента, пусть $$|U^t|=c$$, $$|V^t|=d$$. В этом случае может получиться как $$a^t\equiv 1\pmod n$$, так и $$a^t\double\equiv -1\pmod n$$, но вероятность этого не превосходит $$2/(cd)\leq1/2$$.

    •

    Замечание 3.3. Шаг 2 в алгоритме избыточен, дополнительными соображениями устанавливается, что и для чисел вида $$m^k$$ проверки 1, 2 дают правильный ответ со значительной вероятностью.

    BPP и схемная сложность.

    Теорема 3.3. $$\BPP\subseteq\nuP$$.

    Доказательство. Идея доказательства состоит в том, чтобы усилить оценки вероятностей с $$(1/3,2/3)$$ до $$(\varepsilon,1-\varepsilon)$$. Число $$\varepsilon$$ должно быть настолько мало, чтобы можно было выбрать такое случайное слово $$y_0$$, при котором рассматриваемый предикат из BPP совпадает с $$R(x,y_0)$$.

    Суть здесь в том, что повторение опытов за полиномиальное время экспоненциально уменьшает оценку вероятности ошибки $$\varepsilon$$, но не меняет размер входа $$|x|$$. Поэтому можно добиться выполнения неравенства $$\varepsilon2^{|x|}<1$$. При таком соотношении между $$\eps$$ и $$|x|$$ всегда найдется случайное слово, для которого нет ошибок ни при каких $$x$$.

    Действительно, вспомним наглядное толкование BPP, данное после теоремы 3.1. Если доля слов $$r$$, на которых происходит ошибка, для каждого $$x$$ не превосходит $$\varepsilon$$, то доля тех слов $$r$$, на которых происходит ошибка хотя бы для одного $$x$$, не превосходит $$\varepsilon2^{|x|}<1$$. Значит, найдутся и такие $$r$$, на которых нет ошибок ни при каком $$x$$.

    Это типичное неконструктивное доказательство существования. Мы доказываем, что вероятность того, что объекта с нужными свойствами не существует, меньше 1. Но это и означает, что хотя бы один такой объект существует.

    Страницы:

    В вероятностных МТ (ВМТ), как и в недетерминированных, имеются состояния, из которых возможен переход в несколько (больше одного) состояний. Отличие состоит в том, что состояние, куда ВМТ делает переход, определяется результатом некоторого случайного процесса ("подбрасывания монеты"). Нужно оговорить, какие монеты допускаются. Например, если взять монету, вероятность выпадения герба для которой равна невычислимому числу, то возможности ВМТ, использующей подбрасывание такой монеты, будут больше, чем хотелось бы; она сможет вычислить и некоторые неразрешимые предикаты.

    Обычно считают, что вероятности выпадения одинаковы для обеих сторон монеты, а результат подбрасывания отождествляется с числом 0 или 1.

    Хотя для ВМТ нельзя сказать, какой в точности ответ она выдаст, можно определить вероятность того или иного ответа.

    Определение 3.1. Предикат $$L$$ принадлежит классу BPP, если существуют такие ВМТ $$M$$ и полином $$p(n)$$, что машина $$M$$ заведомо остановится за время, не превосходящее $$p(|x|)$$, причем

    $$L(x)=1$$ $$\Longrightarrow$$ $$M$$ с вероятностью большей $$2/3$$ дает ответ "да";

    $$L(x)=0$$ $$\Longrightarrow$$ $$M$$ с вероятностью большей $$2/3$$ дает ответ "нет".

    Если в этом определении заменить число $$2/3$$ на любое фиксированное число, большее $$1/2$$, класс BPP не изменится. Есть простой способ добиться вероятности, сколь угодно близкой к 1. Возьмем несколько одинаковых машин, запустим их все, а окончательным результатом будем считать мнение большинства. Если вероятность правильного ответа для каждого экземпляра машины равна $$c>1/2$$, то можно доказать, что вероятность правильного ответа после голосования $$n$$ машин не меньше $$1-\lambda^n$$, где $$\lambda=2\sqrt{c(1-c)}<1$$.

    Замечание 3.1. Представить физическую реализацию НМТ очень трудно (вспомним, что нам придется поместить в нее всезнайку Мерлина). А вероятностные машины вполне могут мыслиться как реальные устройства. Поэтому предикаты из класса BPP вполне можно считать реально вычислимыми.

    Класс BPP можно определить и с помощью предикатов от двух переменных, как это было сделано для класса NP.

    Определение 3.2. Предикат $$L$$ принадлежит классу BPP, если существуют такие полином $$q(\cdot)$$ и предикат $$R(\cdot,\cdot)\in\P$$, что

    $$L(x)=1$$ $$\Longrightarrow$$ доля слов $$r$$ длины $$q(|x|)$$, для которых выполнено $$R(x,r)$$, больше $$2/3$$ ;

    $$L(x)=0$$ $$\Longrightarrow$$ доля слов $$r$$ длины $$q(|x|)$$, для которых выполнено $$R(x,r)$$, меньше $$1/3$$.

    Теорема 3.1. Определения 3.1 и 3.2 эквивалентны.

    Доказательство Опр. 3.1 $$\Longrightarrow$$ Полагаем $$q(n)=p(n)$$ (количество подбрасываний монеты не превосходит общего числа действий). Определим предикат $$R(x,r)=$$ "машина $$M$$ на входе $$x$$ дает ответ "да" при указанной в $$r$$ последовательности результатов подбрасываний монеты". Этот предикат по очевидным причинам удовлетворяет определению 3.2.

    Опр. 3.2 $$\Longrightarrow$$ опр. 3.1. Случайно выбираем слово $$r$$ длины $$q(|x|)$$ и подставляем в предикат, затем вычисляем значение предиката. Такая ВМТ удовлетворяет определению 3.1.

    Определение 3.2 допускает следующее наглядное толкование. Отметим на плоскости $$(x,y)$$ точки из множества $$\{(x,y):R(x,y)\wedge(|y|=q(|x|))\}$$. Для $$x=x_0$$ рассмотрим сечение $$\{(x,y):R(x,y)\double\wedge (|y|=q(|x|))\wedge(x=x_0)\}$$ этого множества. Предикат $$R(\cdot,\cdot)$$, участвующий в определении 3.2, обладает таким странным свойством, что мера этого сечения при любом $$x_0$$ либо больше $$2/3$$, либо меньше $$1/3$$. Это разделяет значения $$x$$ на две категории: одна соответствует истинности предиката $$L$$, другая — ложности.

    (рис 3.1)

    Классический пример задачи из BPP представляет проверка простоты числа: дано число $$n$$, требуется определить, простое ли оно. Для этой задачи существует вероятностный алгоритм, работающий за полиномиальное время; он будет сейчас описан.

    Необходимые сведения из теории чисел.

    Подробное изложение элементарной теории чисел содержится в книге [2]. Мы лишь напомним две теоремы, которые будут важны при анализе работы алгоритма проверки простоты числа.

    Малая теорема Ферма. Если $$n$$ — простое и $$n\nmid a$$, то $$a^{n-1}\equiv1\pmod n$$.

    Китайская теорема об остатках. Пусть $$n=uv$$ — разложение числа на взаимно простые множители. Тогда $$\ZZ/n\ZZ=\ZZ/u\ZZ\times\ZZ/v\ZZ$$.

    Другими словами, существует взаимно однозначное соответствие между остатками от деления на $$n$$ и парами остатков от деления на $$u$$ и на $$v$$. {И это соответствие уважает операции сложения и умножения.)

    Из малой теоремы Ферма следует, что $$a^{n-1}\not\equiv1\hskip-1pt\pmod n$$ позволяет утверждать, что $$n$$ — составное (говорят, что $$a$$ является свидетелем непростоты числа $$n$$ ). Это свидетельство косвенное — явного разложения $$n$$ на множители мы не получаем — и сильное: часто достаточно проверки при $$a=2$$!

    Однако проверки малой теоремы Ферма даже при всех $$a$$ может оказаться недостаточно. Алгоритм проверки будет использовать свидетелей еще одного типа: если $$b^2\equiv1\pmod n$$, а $$b\not\equiv\pm1\pmod n$$, то $$n$$ — составное; $$n$$ и $$b-1$$ имеют общий делитель, больший 1. Поэтому свидетели такого вида (вообще говоря, гораздо более редко появляющиеся) позволяют сразу же указать разложение $$n$$ (против простоты которого они свидетельствуют) на два множителя за полиномиальное время (наибольший общий делитель $$(x,y)$$ двух чисел $$x$$ и $$y$$ можно найти за полиномиальное время, см. ниже).

    Необходимые сведения из алгоритмической теории чисел.

    Арифметические операции над числами можно выполнять за полиномиальное время от длины их записи (число $$n$$ записывается $$\lceil\log n\rceil\double=O(\log n)$$ знаками). Например, схема умножения чисел $$n$$, $$m$$ столбиком имеет размер $$O(\log n\log m)$$, растущий квадратично от длины входа. Хотя квадрат от длины входа уже достаточно мал, чтобы быть полиномиальным, заметим, что для умножения $$n$$ -значных чисел есть и более экономные схемы размера $$O(n\log n\log\log n)$$, см.[1, р.7.5] или [7, т. 2, р.4.3.3].

    В модулярной арифметике (арифметике остатков по модулю заданного числа $$q$$ ) можно вычислить $$a^n$$ по модулю $$q$$ схемой полиномиального размера от длины входа $$(a,n,q)$$ (в обычной арифметике даже результат возведения в степень может иметь экспоненциальный размер). Для этого нужно вычислить остатки от степеней $$a^{2^k}$$ последовательным возведением в квадрат и затем перемножить те из полученных чисел, которым соответствуют 1 в двоичной записи числа $$n$$.

    Наибольший общий делитель двух чисел можно найти, пользуясь алгоритмом Евклида, использующим рекурсивно равенство $$(x,y)\double=(y,x\bmod y)$$. Если делить большее число на меньшее, то за каждые два шага длина записи меньшего числа уменьшается на константу.

    Существует также алгоритм проверки того, что из числа извлекается нацело корень $$k$$ -й степени. Это можно сделать, найдя достаточно точно приближенное значение корня и возведя ближайшее к нему целое число в $$k$$ -ю степень. Найти приближенное значение $$\sqrt[k\mkern3mu]{x}$$ можно с помощью рекуррентной последовательности$$a_{n+1}=\frac{1}{k}\left((k-1)a_n+\frac{x}{a_n^{k-1}}\right),$$ если выбрать подходящее значение $$a_0$$. Детали этого (полиномиального) алгоритма оставляются читателю для самостоятельного обдумывания.

    Заметим, что все схемы, о которых шла речь выше, могут быть построены МТ за полиномиальное время. Так что все перечисленные задачи принадлежат классу P.

    Алгоритм проверки простоты.

    Вход: число $$n$$.

    Шаг 1. Проверяем четность $$n$$. Если $$n=2$$, то ответ " $$n$$ — простое", если $$n$$ — четное и больше 2, то ответ " $$n$$ — составное", в противном случае переходим к шагу 2.

    Шаг 2. Проверяем, извлекается ли из $$n$$ нацело корень $$k$$ -й степени при $$k=2,\dots,\lfloor\log_2n\rfloor$$. Если извлекается, то ответ " $$n$$ — составное", иначе переходим к шагу 3.

    Шаг 3. Записываем $$n-1$$ в виде $$2^k\cdot l$$, где $$k>0$$, а $$l$$ — нечетное.

    Шаг 4. Выбираем случайное $$a$$ среди чисел от $$1$$ до $$n$$.

    Шаг 5. Вычисляем $$a^l,\ a^{2l},\ \dots,\ a^{n-1}$$ по модулю $$n$$.

    Проверка 1. Если $$a^{n-1}\not\equiv1\pmod n$$, то ответ " $$n$$ — составное".

    Проверка 2. Если найдено такое $$j$$, для которого $$a^{2^jl}\not\equiv\pm1\pmod n$$, а $$a^{2^{j+1}l}\equiv1\pmod n$$, то ответ " $$n$$ — составное".

    В противном случае ответ " $$n$$ — простое".

    Анализ алгоритма.

    Теорема 3.2. Если $$n$$ — простое, то описанный выше алгоритм всегда (с вероятностью 1) выдает ответ " $$n$$ — простое".

    Если $$n$$ — составное, то ответ " $$n$$ — составное" будет получен с вероятностью $$\geq1/2$$.

    Замечание 3.2. Чтобы получить полиномиальный вероятностный алгоритм проверки простоты числа в смысле определения 3.1, нужно дважды применить приведенный алгоритм. Тогда вероятность ошибки станет меньше $$1/4$$.

    Доказательство (теоремы 3.2). Из сказанного выше следует, что в доказательстве нуждается только второе утверждение.

    Пусть $$n=uv\equiv1\pmod2$$, где $$(u,v)=1$$ (если такого представления нет, то на шаге 2 будет обнаружена непростота). Если $$(a,n)>1$$, то проверка 1 для такого $$a$$ заведомо обнаружит, что $$n$$ — составное. Так что достаточно доказать, что не меньше половины тех $$a$$, которые взаимно просты с $$n$$, обнаруживают непростоту числа.

    Обозначим группу $$(\ZZ/u\ZZ)^*$$ через $$U$$, группу $$(\ZZ/v\ZZ)^*$$ — через $$V$$. Из китайской теоремы об остатках следует, что группа $$(\ZZ/n\ZZ)^*$$ изоморфна $$U\times V$$ (изоморфизм задается естественным образом — вычислением остатков по модулю $$u$$ и по модулю $$v$$ ).

    Рассмотрим множества $$U^k=\{x^k: x\in U\}$$, $$V^k=\{x^k: x\in V\}$$. Это подгруппы в $$U$$ и $$V$$ соответственно (произведение $$k$$ -х степеней есть $$k$$ -я степень, обратный к $$k$$ -й степени есть $$k$$ -я степень). Так что $$|U|/|U^k|$$ — целое число. Более того, отображение $$x\mapsto x^k$$ является гомоморфизмом групп, поэтому число прообразов при этом отображении одинаково для всех элементов $$U^k$$.

    Очевидно, что $$U^{2l}\subseteq U^l$$ (степеней квадратов не больше, чем всех степеней). Поэтому получаем пару невозрастающих цепочек множеств$$U^l\supseteq U^{2l}\supseteq \ldots \supseteq U^{n-1}\supseteq\{1\},\qquad V^l\supseteq V^{2l}\supseteq \ldots \supseteq V^{n-1}\supseteq\{1\}.$$ Дальнейшее рассуждение разбивается на анализ нескольких случаев.

  • Пусть $$U^{n-1}\ne\{1\}$$ или $$V^{n-1}\ne\{1\}$$.

    Чтобы пройти проверку 1 в алгоритме, нужно после возведения в $$(n-1)$$ -ю степень получить пару остатков $$(1,1)$$. Поскольку прообразов каждого числа из $$U^{n-1}\ne\{1\}$$ одинаковое количество, вероятность получения пары $$(1,1)$$ не выше $$1/2$$.

  • Пусть $$U^{n-1}=V^{n-1}=\{1\}$$.

    Поскольку $$l$$ — нечетное, $$-1\in U^{l}\cap V^l$$, т.е. найдется такое $$t=2^s$$, $$0\le s<k$$, что $$U^{2t}\double=V^{2t}=\{1\}$$, а $$U^t\ne\{1\}$$ или $$V^t\ne\{1\}$$.

    Будем доказывать, что с вероятностью не меньше $$1/2$$ в этом месте проверка 2 алгоритма обнаружит, что $$n$$ — составное. В данном случае $$a^{2t}\equiv1 \pmod n$$, так что нужно понять, с какой вероятностью $$a^t$$ не равно $$\pm1$$. Рассмотрим два случая.

  • Одно из множеств $$U^t$$, $$V^t$$ равно $$\{1\}$$. Пусть, например, $$U^t\double=\{1\}$$. В этом случае можно утверждать, что $$a^t\not\equiv-1\pmod n$$ (остатку $$-1$$ при делении на $$n$$ соответствует пара остатков $$(-1,-1)$$ при делении на $$u,v$$ ).

    Можно рассуждать так же, как и в случае 1. С вероятностью не меньше $$1/2$$ получим пару остатков $$(1, \alpha)$$, $$\alpha\ne1$$.

  • Оба множества $$U^t, V^t$$ содержат по крайней мере два элемента, пусть $$|U^t|=c$$, $$|V^t|=d$$. В этом случае может получиться как $$a^t\equiv 1\pmod n$$, так и $$a^t\double\equiv -1\pmod n$$, но вероятность этого не превосходит $$2/(cd)\leq1/2$$.

    •

    Замечание 3.3. Шаг 2 в алгоритме избыточен, дополнительными соображениями устанавливается, что и для чисел вида $$m^k$$ проверки 1, 2 дают правильный ответ со значительной вероятностью.

    BPP и схемная сложность.

    Теорема 3.3. $$\BPP\subseteq\nuP$$.

    Доказательство. Идея доказательства состоит в том, чтобы усилить оценки вероятностей с $$(1/3,2/3)$$ до $$(\varepsilon,1-\varepsilon)$$. Число $$\varepsilon$$ должно быть настолько мало, чтобы можно было выбрать такое случайное слово $$y_0$$, при котором рассматриваемый предикат из BPP совпадает с $$R(x,y_0)$$.

    Суть здесь в том, что повторение опытов за полиномиальное время экспоненциально уменьшает оценку вероятности ошибки $$\varepsilon$$, но не меняет размер входа $$|x|$$. Поэтому можно добиться выполнения неравенства $$\varepsilon2^{|x|}<1$$. При таком соотношении между $$\eps$$ и $$|x|$$ всегда найдется случайное слово, для которого нет ошибок ни при каких $$x$$.

    Действительно, вспомним наглядное толкование BPP, данное после теоремы 3.1. Если доля слов $$r$$, на которых происходит ошибка, для каждого $$x$$ не превосходит $$\varepsilon$$, то доля тех слов $$r$$, на которых происходит ошибка хотя бы для одного $$x$$, не превосходит $$\varepsilon2^{|x|}<1$$. Значит, найдутся и такие $$r$$, на которых нет ошибок ни при каком $$x$$.

    Это типичное неконструктивное доказательство существования. Мы доказываем, что вероятность того, что объекта с нужными свойствами не существует, меньше 1. Но это и означает, что хотя бы один такой объект существует.

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^