Быстрые вычисления с целыми числами и полиномами (стр. 2 из 5)
2.
Если r = 0, то второй столбец матрицы Е даёт вектор (xy) решений уравнения.3. Если r¹ 0, то заменим матрицу Е матрицей
4. Заменим пару чисел (a,b) парой (b,r) и перейдём к шагу 1.
Если обозначить через Еk матрицу Е, возникающую в процессе работы алгоритма перед шагом 2 после k делений с остатком (шаг 1), то в обозначениях из доказательства теоремы 1 в этот момент выполняется векторное равенство (a,b)*Ek = (rk-1,rk). Его легко доказать индукцией по k. Поскольку числа a и b взаимно просты, имеем rn= 1, и это доказывает, что алгоритм действительно даёт решение уравнения ax + by = 1. Буквой n мы обозначили количество делений с остатком, которое в точности такое же, как и в алгоритме Евклида.
Полиномиальные алгоритмы в теории чисел – большая редкость. Да и оценки сложности алгоритмов чаще всего опираются на какие-либо не доказанные, но правдоподобные гипотезы, обычно относящиеся к аналитической теории чисел.
Для некоторых задач эффективные алгоритмы вообще не известны. Иногда в таких случаях всё же можно предложить последовательность действий, которая, «если повезёт», быстро приводит к требуемому результату. Существует класс так называемых вероятностных алгоритмов, которые дают правильный результат, но имеют вероятностную оценку времени работы. Обычно работа этих алгоритмов зависит от одного или нескольких параметров. В худшем случае они работают достаточно долго. Но удачный выбор параметра определяет быстрое завершение работы. Такие алгоритмы, если множество «хороших» значений параметров велико, на практике работают достаточно эффективно, хотя и не имеют хороших оценок сложности.
3. Полиномиальная арифметика
Рассмотрим вероятностный алгоритм, позволяющий эффективно находить решения полиномиальных сравнений по простому модулю. Пусть p – простое число, которое предполагается большим, и f(x)ÎZ[x] – многочлен, степень которого предполагается ограниченной. Задача состоит в отыскании решений сравнения
f(x) º 0 (mod p). (1)
Например, речь может идти о решении квадратичных сравнений, если степень многочлена f(x) равна 2. Другими словами, мы должны отыскать в поле Fp = Z/pZ все элементы, удовлетворяющие уравнению f(x) = 0.
Согласно малой теореме Ферма, все элементы поля Fp являются однократными корнями многочлена xp- x. Поэтому, вычислив наибольший общий делитель d(x) = (xp- x, f(x)), мы найдём многочлен d(x), множество корней которого в поле Fp совпадает с множеством корней многочлена f(x), причём все эти корни однократны. Если окажется, что многочлен d(x) имеет нулевую степень, т. е. лежит в поле Fp, это будет означать, что сравнение (1) не имеет решений.
Для вычисления многочлена d(x) удобно сначала вычислить многочлен c(x)ºxp (mod f(x)), пользуясь алгоритмом, подобным описанному выше алгоритму возведения в степень (напомним, что число p предполагается большим). А затем с помощью аналога алгоритма Евклида вычислить d(x) = (c(x) – x, f(x)). Всё это выполняется за полиномиальное количество арифметических операций.
Таким образом, обсуждая далее задачу нахождения решений сравнения (1) мы можем предполагать, что в кольце многочленов Fp[x] справедливо равенство
f(x) = (x – a1)*…*(x – an), aiÎFp, ai¹aj.
3. 1 Алгоритм нахождения делителей многочлена f(x) в кольце Fp[x]
1. Выберем каким-либо способом элемент dÎ Fp.
2. Вычислим наибольший общий делитель
g(x) = ( f(x), (x + d)(p-1)/2 – 1).
3. Если многочлен g(x) окажется собственным делителем f(x), то многочлен f(x) распадается на два множителя и с каждым из них независимо нужно будет проделать все операции, предписываемые настоящим алгоритмом для многочлена f(x).
4. Если окажется, что g(x) = 1 или g(x) = f(x), следует перейти к шагу 1 и, выбрав новое значение d, продолжить выполнение алгоритма.
Количество операций на шаге 2 оценивается величиной O(lnp), если вычисления проводить так, как это указывалось выше при нахождении d(x). Выясним теперь, сколь долго придётся выбирать числа d, пока на шаге 2 не будет найден собственный делитель f(x).
Количество решений уравнения (t + a1)(p – 1)/2 = (t + a2)(p – 1)/2 в поле Fpне превосходит (p-3)/2. Это означает, что подмножество DÌFp, состоящее из элементов d, удовлетворяющих условиям
(d + a1)(p – 1)/ 2¹ (d + a2)(p – 1)/ 2, d¹ -a1, d¹-a2,
состоит не менее чем (p – 1)/2 из элементов. Учитывая теперь, что каждый ненулевой элемент bÎFp удовлетворяет одному из равенств b(p – 1)/2 = 1, либо b(p – 1)/2 = –1, заключаем, что для dÎD одно из чисел a1, a2 будет корнем многочлена (x + d) (p – 1)/2 – 1, а другое – нет. Для таких элементов d многочлен, определённый на шаге 2 алгоритма, будет собственным делителем многочлена f(x).
Итак, существует не менее (p –1)/2 «удачных» выборов элемента d, при которых на шаге 2 алгоритма многочлен f(x) распадается на два собственных множителя. Следовательно, при «случайном» выборе элемента dÎ Fp, вероятность того, что многочлен не разложится на множители после k повторений шагов алгоритма 1-4, не превосходит 2-k. Вероятность с ростом k убывает очень быстро. И действительно, на практике этот алгоритм работает достаточно эффективно.
Заметим, что при оценке вероятности мы использовали только два корня многочлена f(x). При n > 2 эта вероятность, конечно, ещё меньше. Более тонкий анализ с использованием оценок А. Вейля для сумм характеров показывает, что вероятность для многочлена f(x) не распасться на множители при однократном проходе шагов алгоритма 1-4 не превосходит 2-n + O(p-1/2). Здесь постоянная в O(.) зависит от n. В настоящее время известно элементарное доказательство оценки А. Вейля.
Если в сравнении (1) заменить простой модуль p составным модулем m, то задача нахождения решений соответствующего сравнения становится намного более сложной. Известные алгоритмы её решения основаны на сведении сравнения к совокупности сравнений (1) по простым модулям – делителям m, и, следовательно, они требуют разложения числа m на простые сомножители, что, как уже указывалось, является достаточно трудоёмкой задачей.
3.2 Произведение и возведение в степень многочленов, заданных массивами
Условимся представлять многочлены массивами, индексированными, начиная с 0, в которых элемент с индексом i означает коэффициент многочлена степени i
type
Polynome=array[1..Nmax] of Ring_Element;
Следующий алгоритм даёт функцию умножения двух многочленов и , где многочлен степени (который даёт результат в конце алгоритма) должен быть предварительно инициализирован нулём.
fori:= 0 to degPdo
forj:= 0 to degQ do
R[i+j]:=R[i+j]+P[i]*Q[i];
Изучая предыдущий алгоритм, устанавливаем, что его сложность как по числу перемножений, так и сложений, равна произведению высот двух многочленов: (degP+ 1)(degQ+ 1), но в этом алгоритме, который не учитывает случай нулевых коэффициентов, можно рассматривать высоту многочлена как число всех коэффициентов. Значит, возможно улучшить предыдущий алгоритм, исключив все ненужные перемножения:
fori:= 0 to degPdo
if P[i] ¹ 0 then
forj:= 0 to degQ do
if Q[j] ¹ 0 then
R[i+j]:=R[i+j]+P[i]Q[i];
Очень просто вычислить сложность алгоритма возведения в степень последовательными умножениями, если заметить, что когда P – многочлен степени d, то Pi – многочлен степени id. Если обозначить Cmul(n) сложность вычисления Pn, то рекуррентное соотношение Cmul(i+ 1) = Cmul(i) + (d +1)(id +1) даёт нам:
 |
Cmul(n) = =
Что касается возведения в степень с помощью дихотомии (т.е. повторяющимися возведениями в квадрат), вычисления несколько сложнее: зная , вычисляем с мультипликативной сложностью. Как следствие имеем:  |
Csqr(2l) = = =
 |
=
Предварительное заключение, которое можно вывести из предыдущих вычислений, складывается в пользу дихотомического возведения в степень: если n есть степень двойки (гипотеза ad hoc), этот алгоритм ещё выдерживает конкуренцию, даже если эта победа гораздо скромнее в данном контексте (n2d2/3 против n2d2/2), чем когда работаем в Z/pZ (2log2n против n).