Быстрые вычисления с целыми числами и полиномами
енты, удовлетворяющие уравнению 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. Выберем каким-либо способом элемент ( ( Fp.
2. Вычислим наибольший общий делитель
g(x) = ( f(x), (x + ()(p-1)/2 – 1).
3. Если многочлен g(x) окажется собственным делителем f(x), то многочлен
f(x) распадается на два множителя и с каждым из них независимо нужно
будет проделать все операции, предписываемые настоящим алгоритмом для
многочлена f(x).
4. Если окажется, что g(x) = 1 или g(x) = f(x), следует перейти к шагу 1 и,
выбрав новое значение (, продолжить выполнение алгоритма.
Количество операций на шаге 2 оценивается величиной O(ln p), если
вычисления проводить так, как это указывалось выше при нахождении d(x).
Выясним теперь, сколь долго придётся выбирать числа (, пока на шаге 2 не
будет найден собственный делитель f(x).
Количество решений уравнения (t + a1)(p – 1)/2 = (t + a2)(p – 1)/2 в
поле Fp не превосходит (p-3)/2. Это означает, что подмножество D ( Fp,
состоящее из элементов (, удовлетворяющих условиям
(( + a1)(p – 1)/ 2 ( (( + a2)(p – 1)/ 2, ( ( -a1, ( ( -a2,
состоит не менее чем (p – 1)/2 из элементов. Учитывая теперь, что каждый
ненулевой элемент b(Fp удовлетворяет одному из равенств b(p – 1)/2 = 1,
либо b(p – 1)/2 = –1, заключаем, что для ( ( D одно из чисел a1, a2
будет корнем многочлена (x + () (p – 1)/2 – 1, а другое – нет. Для таких
элементов ( многочлен, определённый на шаге 2 алгоритма, будет собственным
делителем многочлена f(x).
Итак, существует не менее (p –1)/2 «удачных» выборов элемента (, при
которых на шаге 2 алгоритма многочлен f(x) распадается на два собственных
множителя. Следовательно, при «случайном» выборе элемента ( ( 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;
Следующий алгоритм даёт функцию умножения двух многочленов и , где
многочлен степени (который даёт результат в конце алгоритма) должен быть
предварительно инициализирован нулём.
for i:= 0 to degP do
for j:= 0 to degQ do
R[i+j]:=R[i+j]+P[i](Q[i];
Изучая предыдущий алгоритм, устанавливаем, что его сложность как по
числу перемножений, так и сложений, равна произведению высот двух
многочленов: (deg P + 1)(degQ + 1), но в этом алгоритме, который не
учитывает случай нулевых коэффициентов, можно рассматривать высоту
многочлена как число всех коэффициентов. Значит, возможно улучшить
предыдущий алгоритм, исключив все ненужные перемножения:
for i:= 0 to degP do
if P[i] ( 0 then
for j:= 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 (2log2 n против n).
Но мы не учли корректирующие перемножения, которые должны быть
выполнены, когда показатель не является степенью двойки. Если n = 2l+1 – 1,
нужно добавить к последовательным возведениям в квадрат перемножения всех
полученных многочленов. Умножение многочлена степени (2i-1)d на
многочлен степени 2id вносит свой вклад из ((2i – 1)d + 1)( 2i d +
1) умножений, которые, будучи собранными по всем корректирующим
вычислениям, дают дополнительную сложность:
= =
=
Теперь можно заключить, что дихотомическое возведение в степень не
всегда является лучшим способом для вычисления степени многочлена с помощью
перемножений многочленов. Число перемножений базисного кольца, которые
необходимы, Csqr(n), - в действительности заключено между (
) и т.е. между n2d2/3 и 2n2d2/3,
тогда как простой алгоритм требует всегда n2d2/2 перемножений. В частности,
если исходный многочлен имеет степень, большую или равную 4, возведение в
степень наивным методом требует меньше перемножений в базисном кольце, чем
бинарное возведение в степень, когда n имеет форму 2l – 1.
Можно довольно просто доказать, что если n имеет вид 2l +2l – 1 + c
(выражения, представляющие двоичное разложение n), то метод вычисления
последовательными перемножениями лучше метода, использующего возведение в
квадрат (этот последний метод требует корректирующего счёта ценой, по
крайней мере, n2d2/9). Всё это доказывает, что наивный способ является
лучшим для этого класса алгоритмов, по крайней мере, в половине случаев.
Действительно, МакКарти [3] доказал, что дихотомический алгоритм
возведения в степень оптимален среди алгоритмов, оперирующих повторными
умножениями, если действуют с плотными многочленами (антоним к разреженным)
по модулю m, или с целыми и при условии оптимизации возведения в квадрат
для сокращения его сложности наполовину (в этом случае сложность
действительно падает приблизительно до n2d2/6 + n2d2/3 = n2d2/2).
3.3 Небольшие оптимизации для произведений многочленов
В принципе вычисление произведения двух многочленов степеней n и m
соответственно требует (n +1)( m +1) элементарных перемножений. Алгоритм
оптимизации возведения в квадрат состоит просто в применении формулы
квадрата суммы:
что даёт n +1 умножений для первого члена и n( n +1)/2 – для второго, или в
целом (n +1)( n +2)/2 умножений, что близко к половине предусмотренных
умножений, когда n большое.
Для произведения двух многочленов первой степени P = aX + b и Q = cX + d
достаточно легко находим формулы U = ac, W = bd, V = (a + b)(c + d) и PQ =
=UX2 + (V – U – W)X +W, в которых появляются только три элементарных
умножения, но четыре сложения. Можно рекурсивно применить этот процесс для
умножения двух многочленов P и Q степени 2l – 1, представляя их в виде
и применяя предыдущие формулы для вычисления PQ в
зависимости от A, B, C и D, где каждое произведение AB, CD и (A + B)(C + D)
вычисляется с помощью рекурсивного применения данного метода (это метод
Карацубы). Всё это даёт мультипликативную
| |  скачать работу |
Быстрые вычисления с целыми числами и полиномами |
