84245 (675642), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

f(x) = (x – a₁)…(x – a_n), a_iF_p, a_i  a_j.

3. 1 Алгоритм нахождения делителей многочлена f(x) в кольце F_p[x]

1. Выберем каким-либо способом элемент   F_p.

2. Вычислим наибольший общий делитель

g(x) = ( f(x), (x + )^(p-1)/2 – 1).

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

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

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

Количество решений уравнения (t + a₁)^{(p – 1)/2} = (t + a₂)^{(p – 1)/2} в поле F_p не превосходит (p-3)/2. Это означает, что подмножество D  F_p, состоящее из элементов , удовлетворяющих условиям

( + a₁)^{(p – 1)/ 2}  ( + a₂)^{(p – 1)/ 2},   -a₁,   -a₂,

состоит не менее чем (p – 1)/2 из элементов. Учитывая теперь, что каждый ненулевой элемент bF_p удовлетворяет одному из равенств b^{(p – 1)/2} = 1, либо b^{(p – 1)/2} = –1, заключаем, что для   D одно из чисел a₁, a₂ будет корнем многочлена (x + ) ^{(p – 1)/2} – 1, а другое – нет. Для таких элементов  многочлен, определённый на шаге 2 алгоритма, будет собственным делителем многочлена f(x).

Итак, существует не менее (p –1)/2 «удачных» выборов элемента , при которых на шаге 2 алгоритма многочлен f(x) распадается на два собственных множителя. Следовательно, при «случайном» выборе элемента   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 на простые сомножители, что, как уже указывалось, является достаточно трудоёмкой задачей.

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, то Pⁱ – многочлен степени id. Если обозначить C_mul(n) сложность вычисления Pⁿ, то рекуррентное соотношение C_mul(i + 1) = C_mul(i) + (d +1)(id +1) даёт нам:

C_mul(n) = =

Ч то касается возведения в степень с помощью дихотомии (т.е. повторяющимися возведениями в квадрат), вычисления несколько сложнее: зная , вычисляем с мультипликативной сложностью. Как следствие имеем:

C_sqr(2^l) = = =

=

Предварительное заключение, которое можно вывести из предыдущих вычислений, складывается в пользу дихотомического возведения в степень: если n есть степень двойки (гипотеза ad hoc), этот алгоритм ещё выдерживает конкуренцию, даже если эта победа гораздо скромнее в данном контексте (n²d²/3 против n²d²/2), чем когда работаем в Z/pZ (2log₂ n против n).

Н о мы не учли корректирующие перемножения, которые должны быть выполнены, когда показатель не является степенью двойки. Если n = 2l+1 – 1, нужно добавить к последовательным возведениям в квадрат перемножения всех полученных многочленов. Умножение многочлена степени (2ⁱ-1)d на многочлен степени 2ⁱd вносит свой вклад из ((2ⁱ – 1)d + 1)( 2ⁱ d + 1) умножений, которые, будучи собранными по всем корректирующим вычислениям, дают дополнительную сложность:

= =

=

Т еперь можно заключить, что дихотомическое возведение в степень не всегда является лучшим способом для вычисления степени многочлена с помощью перемножений многочленов. Число перемножений базисного кольца, которые необходимы, C_sqr(n), - в действительности заключено между ( ) и т.е. между n²d²/3 и 2n²d²/3, тогда как простой алгоритм требует всегда n²d²/2 перемножений. В частности, если исходный многочлен имеет степень, большую или равную 4, возведение в степень наивным методом требует меньше перемножений в базисном кольце, чем бинарное возведение в степень, когда n имеет форму 2^l – 1.

Можно довольно просто доказать, что если n имеет вид 2^l +2^{l – 1} + c (выражения, представляющие двоичное разложение n), то метод вычисления последовательными перемножениями лучше метода, использующего возведение в квадрат (этот последний метод требует корректирующего счёта ценой, по крайней мере, n²d²/9). Всё это доказывает, что наивный способ является лучшим для этого класса алгоритмов, по крайней мере, в половине случаев.

Действительно, МакКарти [3] доказал, что дихотомический алгоритм возведения в степень оптимален среди алгоритмов, оперирующих повторными умножениями, если действуют с плотными многочленами (антоним к разреженным) по модулю m, или с целыми и при условии оптимизации возведения в квадрат для сокращения его сложности наполовину (в этом случае сложность действительно падает приблизительно до n²d²/6 + n²d²/3 = n²d²/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 = =UX² + (V – U – W)X +W, в которых появляются только три элементарных умножения, но четыре сложения. Можно рекурсивно применить этот процесс для умножения двух многочленов P и Q степени 2^l – 1, представляя их в виде и применяя предыдущие формулы для вычисления PQ в зависимости от A, B, C и D, где каждое произведение AB, CD и (A + B)(C + D) вычисляется с помощью рекурсивного применения данного метода (это метод Карацубы). Всё это даёт мультипликативную сложность (2^l) и аддитивную сложность (2^l) такие, что:

 (2^l) = 3(2^{l – 1}),…, (2) = 3(1), (1) = 1,

(2^l) = 3(2^{l – 1}) + 32^l,…, (2) = 3(1) + 6, (1) = 1.

В этой последней формуле член 32^l представляет собой число элементарных сложений, необходимых, чтобы сделать два сложения многочленов степени 2^{l – 1} – 1 (a + b и c + d) и два вычитания многочленов степени 2^l – 1 (U – V – W). Суммируя каждое из этих выражений, находим для n, являющегося степенью двойки:

(n) = n^log3/log2  n^1,585 и (2) =7 n^log3/log2 – 6n.

К сожалению, этот принцип остаётся теоретическим, и на его основе нужно построить итерационный алгоритм, чтобы получить разумную эффективность (цена управления рекурсией очень велика).

3.4 Вычисление многочленов

Рассмотрим общую задачу вычисления многочлена n-й степени

u(x) = u_nxⁿ + u_{n – 1}x^{n – 1} + ... + u₁x + u₀, u_n  0, (1)

3.4.1 Схема Горнера

u(x) = (…(u_nx + u_{n – 1})x + …)x + u₀. (2)

Весь этот процесс требует n умножений и n сложений.

Было предложено несколько обобщений схемы Горнера. Посмотрим сначала, как вычисляется в случае, когда – комплексное число, а коэффициенты вещественны. Комплексное сложение и умножение можно очевидным образом свести к последовательности обычных операций над вещественными числами:

вещественное + комплексное требует 1 сложение,

комплексное + комплексное требует 2 сложения,

Характеристики

Список файлов реферата