T n +1 ( x )+ T n -1 ( x )=2 cos (
n q ) cos ( q )=2 xT n ( x );
T n+1 (x)=2xT n (x)-T n-1 (x)
Применяя полученные
формулы можно найти любой полином Чебышева.
Например, Т 3 ( x )=2 xT 2 ( x )- T 1 ( x ). Подставляя
значения T 2 ( х ) и Т 1 ( х ) имеем
Т 3 ( х )=2х(2х 2 -1)-х=4х 3 -3х. Графически
первые 10 полиномов Чебышева изображены
ниже. Последующие полиномы по-прежнему
колеблются между +1 и -1, причём период
колебания уменьшаются с ростом порядка
полинома. Преобразования q=arccos(x) можно
рассмотреть как проекцию пересечений
полукруга с множеством прямых, имеющих
углы равные между собой. Таким образом,
множество точек x j , на котором
система чебышевских многочленов T n ( x ) ортогональна,
есть: ( j =0, 1, 2, …, N -1). Так как T n ( x ) есть, по
существу, cos ( n q ), то они являются равноколеблющимися
функциями, и так как они многочлены, то
обладают всеми свойствами, которые имеют
ортогональные многочлены
Чебышев доказал, что из всех многочленов
Рn (x) степени
n старшим коэффициентом 1, у многочлена
точная верхняя грань абсолютных значений
на интервале -1 Ј x Ј 1 наименьшая. Так как
верхняя грань T n (x )=1, указанная
верхняя грань равна.
- Полиномиальная арифметика
Рассмотрим вероятностный
алгоритм, позволяющий эффективно находить
решения полиномиальных сравнений по
простому модулю. Пусть 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. Выберем каким-либо способом
элемент ( (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)
Что касается возведения
в степень с помощью дихотомии (т.е.
повторяющимися возведениями в квадрат),
вычисления несколько сложнее: зная,
вычисляем с мультипликативной сложностью.
Предварительное
заключение, которое можно
вывести из предыдущих
вычислений, складывается в
пользу дихотомического возведения
в степень: если 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) вычисляется
с помощью рекурсивного применения
данного метода (это метод Карацубы).
Всё это даёт мультипликативную
сложность ((2l) и аддитивную сложность
((2l) такие, что:
((2l) = 3((2l – 1),…, ((2) = 3((1), ((1) = 1,
((2l) = 3((2l – 1) + 3(2l,…, ((2) = 3((1) + 6, ((1) = 1.
В этой последней
формуле член 3(2l представляет собой
число элементарных сложений, необходимых,
чтобы сделать два сложения
многочленов степени 2l – 1 – 1 (a + b и
c + d) и два вычитания многочленов степени
2l – 1 (U –V – W). Суммируя каждое
из этих выражений, находим
для n, являющегося степенью двойки:
((n) = nlog3/log2
( n1,585 и
((2) =7 nlog3/log2 – 6n.
К сожалению, этот принцип остаётся
теоретическим, и на его основе
нужно построить итерационный алгоритм,
чтобы получить разумную эффективность
(цена управления рекурсией очень велика).
Cписок литературы
1. Введение в криптографию
под общей редакцией Ященко,
М.: МЦНМО: «Черо», 1999.
2. Алгебраическая алгоритмика,
Ноден П., Китте К., М.: «Мир», 1999.