долго. Но удачный выбор параметра определяет быстрое завершение работы. Такие алгоритмы, если множество «хороших» значений параметров велико, на практике работают достаточно эффективно, хотя и не имеют хороших оценок сложности.

Мы будем иногда использовать слова детерминированный алгоритм, чтобы отличать алгоритмы в обычном смысле от вероятностных алгоритмов.

Как пример, рассмотрим вероятностный алгоритм, позволяюший эффективно находить решения полиномиальных сравнений по простому модулю. Пусть р - простое число, которое предполагается большим, и /(ж) £ Ъ[х\ - многочлен, степень которого предполагается ограниченной. Задача состоит в отыскании решений сравнения

Например, речь может идти о решении квадратичных сравнений, если степень многочлена /(ж) равна 2. Другими словами, мы должны отыскать в поле ¥р = Ъ/рЪ все элементы, удовлетворяюшие уравнению /(ж) = 0.

Согласно малой теореме Ферма, все элементы поля ¥р являются однократными корнями многочлена хр - ж. Поэтому, вычислив наибольший обший делитель d(x) = (хр - х. /(ж)), мы найдем многочлен d(x). множество корней которого в поле ¥р совпадает с множеством корней многочлена /(ж), причем все эти корни однократны. Если окажется, что многочлен d(x) имеет нулевую степень, т. е. лежит в поле ¥р. это будет означать, что сравнение (8) не имеет решений.

Для вычисления многочлена d(x) удобно сначала вычислить многочлен с(ж) = хр (mod /(ж)), пользуясь алгоритмом, подобным описанному выше алгоритму возведения в степень (напомним, что число р предполагается большим). А затем с помошью аналога алгоритма Евклида вычислить d(x) = (с(ж) -ж. /(ж)). Всё это выполняется за полиномиальное количество арифметических операций.

Таким образом, обсуждая далее задачу нахождения решений сравнения (8). мы можем предполагать, что в кольце многочленов ¥р[х] справедливо равенство

4. Алгоритм нахождения делителей многочлена /(ж) в кольце ¥р[х].

1)Выберем каким-либо способом элемент 8 6 ¥р.

2)Вычислим наибольший общий делитель д(х) = (/(ж), (ж+ 5) 2 - 1).

3)Если многочлен д(х) окажется собственным делителем /(ж), то

f(x) = (ж - ах) ... (ж - ап), аг £ ¥р.аг ф аГ

многочлен /(ж) распадётся на два множителя и с каждым из них независимо нужно будет проделать все операции, предписываемые настоящим алгоритмом для многочлена /(ж).

4) Если окажется, что g(x) = 1 или д(х) = /(ж), следует перейти к шагу 1 и. выбрав новое значение 8. продолжить выполнение алгоритма.

Количество операций на шаге 2 оценивается величиной 0(Ыр). если вычисления проводить так. как это указывалось выше при нахождении d(x). Выясним теперь, сколь долго придётся выбирать числа 8. пока на шаге 2 не будет найден собственный делитель /(ж).

р -1р -1

Количество решений уравнения (t + а\)~ = (t + 6(2) в поле ¥р не превосходит Это означает, что подмножество D с¥р: состоящее из элементов 8. удовлетворяюших условиям

(8 + ai)~2~ ф (8 + а,2)~2~, 8 ф-а\. 8 ф-а2:

состоит не менее, чем из элементов. Учитывая теперь, что каждый

ненулевой элемент 6 £ Fp удовлетворяет одному из равенств 6 2 = 1.

либо= -1. заключаем, что для 8 £ D одно из чисел а\. а2 будет

корнем многочлена (ж + 8)~ - 1, а другое - нет. Для таких элементов 8 многочлен д(ж). определённый на шаге 2 алгоритма, будет собственным делителем многочлена /(ж).

Итак, существует не менее «удачных» выборов элемента 8. при которых на шаге 2 алгоритма многочлен /(ж) распадётся на два собственных множителя. Следовательно, при «случайном» выборе элемента 8 £ ¥р. вероятность того, что многочлен не разложится на множители после к повторений шагов алгоритма 1-4. не превосходит 2~к. Вероятность с ростом к убывает очень быстро. И действительно, на практике этот алгоритм работает достаточно эффективно.

Заметим, что при опенке вероятности мы использовали только два корня многочлена /(ж). При п > 2 эта вероятность, конечно, ешё меньше. Более тонкий анализ с использованием оценок А. Вейля для сумм характеров показывает, что вероятность для многочлена /(ж) не распасться на множители при однократном проходе шагов алгоритма 1-4. не превосходит 2~п + 0{р~1!2). Здесь постоянная в 0{) зависит от п. Детали доказательства см. в [26]. В настоящее время известно элементарное доказательство опенки А. Вейля (см. [11]).

В книге [7] описывается принадлежащий Берлекэмпу детерминированный алгоритм решения сравнения (8). требуюший 0(рп3) арифметических операций. Ясно, что он практически бесполезен при больших р. а вот при маленьких р и не очень больших п он работает не очень долго.

Если в сравнении (8) заменить простой модуль р составным модулем то. то задача нахождения решений соответствующего сравнения становится намного более сложной. Известные алгоритмы её решения основаны на сведении сравнения к совокупности сравнений (8) по простым модулям - делителям то. и. следовательно, они требуют разложения числа то на простые сомножители, что. как уже указывалось, является достаточно трудоемкой задачей.

3. Как отличить составное число от простого

Существует довольно эффективный способ убедиться, что заданное число является составным, не разлагая это число на множители. Согласно малой теореме Ферма, если число N простое, то для любого целого а. не делящегося на N. выполняется сравнение

а-1 = 1 (mod N).(9)

Если же при каком-то а это сравнение нарушается, можно утверждать, что N - составное. Проверка (9) не требует больших вычислений, это следует из алгоритма 1. Вопрос только в том. как найти для составного N целое число а. не удовлетворяющее (9). Можно, например, пытаться найти необходимое число а. испытывая все целые числа подряд, начиная с 2. Или попробовать выбирать эти числа случайным образом на отрезке 1 < а < N.

К сожалению, такой подход не всегда даёт то. что хотелось бы. Имеются составные числа N. обладающие свойством (9) для любого целого а с условием (a.N) = 1. Такие числа называются числами Кармайкла. Рассмотрим, например, число 561 = 3 • 11 17. Так как 560 делится на каждое из чисел 2. 10. 16. то с помощью малой теоремы Ферма легко проверить, что 561 есть число Кармайкла. Можно доказать (Carmichael. 1912). что любое из чисел Кармайкла имеет вид N = р\ ... pr. г 3. где все простые pi различны, причем N - 1 делится на каждую разность Pi - 1. Лишь недавно, см. [12]. была решена проблема о бесконечности множества таких чисел.

В 1976 г. Миллер предложил заменить проверку (9) проверкой несколько иного условия. Детали последующего изложения можно найти в [10]. Если N - простое число. N - 1 = 2s t, где t нечётно, то согласно малой теореме Ферма для каждого а с условием (a, N) = 1 хотя бы одна из скобок в произведении

(а* - 1) (а* + 1) (а2* + 1) • ... • {а2"4 + 1) = aN~1 - 1