Вычисления результанта 2-ч полиномов

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, указанная верхняя грань равна.

 

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. Выберем каким-либо способом элемент ( (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.