Рассмотрим вероятностный алгоритм, позволяющий эффективно находить решения полиномиальных сравнений по простому модулю. Пусть p – простое число, которое предполагается большим, и f (x)ÎZ[ x ] – многочлен, степень которого предполагается ограниченной. Задача состоит в отыскании решений сравнения
f (x) º 0 (mod p). (1)
Например, речь может идти о решении квадратичных сравнений, если степень многочлена f (x) равна 2. Другими словами, мы должны отыскать в поле F p = Z/ p Z все элементы, удовлетворяющие уравнению f (x) = 0.
Согласно малой теореме Ферма, все элементы поля F p являются однократными корнями многочлена xp - x. Поэтому, вычислив наибольший общий делитель d (x) = (xp - x, f (x)), мы найдём многочлен d (x), множество корней которого в поле F p совпадает с множеством корней многочлена f (x), причём все эти корни однократны. Если окажется, что многочлен d (x) имеет нулевую степень, т. е. лежит в поле F p, это будет означать, что сравнение (1) не имеет решений.
|
|
Для вычисления многочлена d (x) удобно сначала вычислить многочлен c (x)º xp (mod f (x)), пользуясь алгоритмом, подобным описанному выше алгоритму возведения в степень (напомним, что число p предполагается большим). А затем с помощью аналога алгоритма Евклида вычислить d (x) = (c (x) – x, f (x)). Всё это выполняется за полиномиальное количество арифметических операций.
Таким образом, обсуждая далее задачу нахождения решений сравнения (1) мы можем предполагать, что в кольце многочленов F p [ x ] справедливо равенство
f (x) = (x – a1)*…*(x – an), ai ÎF p, ai ¹ aj.
3. 1 Алгоритм нахождения делителей многочлена f (x) в кольце F p [ x ]
1. Выберем каким-либо способом элемент d Î F p.
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 (ln p), если вычисления проводить так, как это указывалось выше при нахождении d (x). Выясним теперь, сколь долго придётся выбирать числа d, пока на шаге 2 не будет найден собственный делитель f (x).
Количество решений уравнения (t + a1)( p – 1)/2 = (t + a2)( p – 1)/2 в поле F p не превосходит (p -3)/2. Это означает, что подмножество D Ì F p, состоящее из элементов d, удовлетворяющих условиям
(d + a1)(p – 1)/ 2 ¹ (d + a2)(p – 1)/ 2, d ¹ - a1, d ¹ - a2,
состоит не менее чем (p – 1)/2 из элементов. Учитывая теперь, что каждый ненулевой элемент b ÎF p удовлетворяет одному из равенств 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 Î F p, вероятность того, что многочлен не разложится на множители после 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 на простые сомножители, что, как уже указывалось, является достаточно трудоёмкой задачей.
Произведение и возведение в степень многочленов, заданных массивами
Условимся представлять многочлены массивами, индексированными, начиная с 0, в которых элемент с индексом i означает коэффициент многочлена степени i
Type
Polynome =array [1.. Nmax ] of Ring_Element;
Следующий алгоритм даёт функцию умножения двух многочленов и, где многочлен степени (который даёт результат в конце алгоритма) должен быть предварительно инициализирован нулём.
for i:= 0 to deg P do
for j:= 0 to deg Q do
R [ i + j ]:= R [ i + j ]+ P [ i ]* Q [ i ];
Изучая предыдущий алгоритм, устанавливаем, что его сложность как по числу перемножений, так и сложений, равна произведению высот двух многочленов: (deg P + 1)(deg Q + 1), но в этом алгоритме, который не учитывает случай нулевых коэффициентов, можно рассматривать высоту многочлена как число всех коэффициентов. Значит, возможно улучшить предыдущий алгоритм, исключив все ненужные перемножения:
for i:= 0 to deg P do
if P [ i ] ¹ 0 then
for j:= 0 to deg Q 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 (2 l) = = =
=
Предварительное заключение, которое можно вывести из предыдущих вычислений, складывается в пользу дихотомического возведения в степень: если n есть степень двойки (гипотеза ad hoc), этот алгоритм ещё выдерживает конкуренцию, даже если эта победа гораздо скромнее в данном контексте (n 2 d 2/3 против n 2 d 2/2), чем когда работаем в Z/ p Z (2log2 n против n).
Но мы не учли корректирующие перемножения, которые должны быть выполнены, когда показатель не является степенью двойки. Если n = 2l+1 – 1, нужно добавить к последовательным возведениям в квадрат перемножения всех полученных многочленов. Умножение многочлена степени (2 i -1) d на многочлен степени 2 id вносит свой вклад из ((2 i – 1) d + 1)(2 i d + 1) умножений, которые, будучи собранными по всем корректирующим вычислениям, дают дополнительную сложность:
|
|
= =
=
Теперь можно заключить, что дихотомическое возведение в степень не всегда является лучшим способом для вычисления степени многочлена с помощью перемножений многочленов. Число перемножений базисного кольца, которые необходимы, Csqr (n), - в действительности заключено между ( ) и т.е. между n 2 d 2/3 и 2 n 2 d 2/3, тогда как простой алгоритм требует всегда n 2 d 2/2 перемножений. В частности, если исходный многочлен имеет степень, большую или равную 4, возведение в степень наивным методом требует меньше перемножений в базисном кольце, чем бинарное возведение в степень, когда n имеет форму 2 l – 1.
Можно довольно просто доказать, что если n имеет вид 2 l +2 l – 1 + c (выражения, представляющие двоичное разложение n), то метод вычисления последовательными перемножениями лучше метода, использующего возведение в квадрат (этот последний метод требует корректирующего счёта ценой, по крайней мере, n 2 d 2/9). Всё это доказывает, что наивный способ является лучшим для этого класса алгоритмов, по крайней мере, в половине случаев.
Действительно, МакКарти [3] доказал, что дихотомический алгоритм возведения в степень оптимален среди алгоритмов, оперирующих повторными умножениями, если действуют с плотными многочленами (антоним к разреженным) по модулю m, или с целыми и при условии оптимизации возведения в квадрат для сокращения его сложности наполовину (в этом случае сложность действительно падает приблизительно до n 2 d 2/6 + n 2 d 2/3 = n 2 d 2/2).
|
|