Для выполнения обратного перехода от набора чисел (ui,u2,... ,uk) к числу u применяется китайская теорема об остатках.

Теорема. Пусть M = mim2 .. .m чиела mi попарно взаимно просты, и

ci = mi ... mi-imi+i ... mk = M/mi, di = c-1 mod mi,

i = 1,... ,k. Тогда решение системы сравнений

u = ui (mod mi), i = 1,...,k,

u = cidiui mod M.

Доказательство легко вытекает из следующих свойств выбранных чисел:

cidi = 0 (mod mj) прmj = i,

ci di = 1 (mod mi), i,j = 1,...,k. □ u

]Г (O((k - 1)M(Ъ)) + TxEA(b)) + M(kb) =

= O((k2M (Ъ) + kTxEA(b) + M (kb))) =

= O(k2M (Ъ) + kTxEA(b))

двоичных операций, где через Тхеа{Ь) обозначена сложность нахождения обратного элемента в кольце Zm \og mi=Ъ, с помощью расширенного алгоритма Евклида. Трудоемкость можно уменьшить, если аналогично предыдущему случаю воспользоваться техникой «разделяй и властвуй», применяя каждый раз аналог данной формулы при k = толу чается оценка O(M (kb) log k + kTxEA(b)).

u = qi + q2mi + mim2 + ... + qk mi ... mk-i,

где числа qi,q2,... ,qk вычисляются в процессе выполнения следующего алгоритма:

с =1, u = u1 mod m1; i = 1 k - 1 begin

с = с • mi;

d = с-1 mod mi+i;

q = d(ui+i - u) mod mi+i;

u = u + q,

Доказательство корректности данного алгоритма нахождения чис-

качестве упражнения.

Хотя трудоемкость вычисления по этой формуле такая же, как и для исходной формулы, приведенной в теореме, и составляет O(k2M(Ъ) + kTxEA(b)) двоичных операций, данная формула во многих случаях оказывается более удобной. Это вызвано тем, что процесс восстановления решения системы

u = ui (mod mi), i = 1,...,k,

осуществляется в ней последовательно: сначала для первых двух сравнений, затем для первых трех, и так далее до получения общего решения. Если к системе добавить еще одно сравнение, то ход вычислений не изменится, и надо будет выполнить всего один дополнительный шаг. В то же время в случае исходной формулы добавление еще одного сравнения полностью меняет схему вычислений.

§ 6. Вычисления с многочленами

Между вычислениями в кольце многочленов над произвольным кольцом R и в кольце целых чисел, записанных в какой-либо системе счисления, много общего. Они выполняются по похожим формулам, а отличие заключается лишь в том, что для чисел необходимо учитывать знаки переноса от младших разрядов к старшим, в то время как в случае многочленов никаких переносов при операциях с коэффициентами многочленов не возникает - и исходные величины и значения лежат в кольце R. Поэтому вычисления с многочленами в чем-то даже проще, чем вычисления с целыми числами.

Сложность операций с многочленами обычно оценивают коли-

коэффициентами. Если известна битовая сложность операций в поле, то можно также оценить результирующую битовую сложность операций с многочленами. Чтобы отличать арифметическую сложность от битовой в оценках мы будем использовать символы Oa( ) и Ob( ).

цо. Рассмотрим хорошо известный алгоритм Руффини-Горнера для вычисления значения многочлена

/ (ж) = а„хп + а„-1Хп-1 + + а1 x + ао

над кольцом точке x = 6. Он основан на следующем представлении многочлена

/ (x) = ((а„ x + а„-1 )x + + а1 )x + ао

и заключается в последовательном вычислении значений po, p1, , pn по формулам

po = а„,

pi = pi-16 + ап-i,

i = 1, , даее число pn и будет искомым значением многочлена. Арифметическая сложность алгоритма, очевидно, равна Oa(n).

вается кольцо целых чисел, можно оценить выражением Ob (nml), где m

в записи наибольшего коэффициента и числа тасло l = (n + 2)m

i = 1, , олучается оценка Ob(n2m2).

Алгоритм Руффини-Горнера позволяет получить не только значение /(6) = pn. Как показывает следующая теорема, величины po,pl,,pn-l являются в точности коэффициентами многочлена,

/(x) (x - 6)

Теорема. Справедливо равенство

/(x) = (x - 6 p„-i-1 + /(6)

Доказательство. Имеем

(x - p„-i-1xi + / (6) =

Vi=o /

]rp„-i-16xM + / (6)

]rp"-i-1xi+1

pn-ix

]rp„-i-16x4 + / (6) =

Е (pn-i - pn-i-16)xi - pn-16 + /(6) =

aixi - pn-16 + (pn-16 + ao) =

aixi = / (x)

□

§ 7. Дискретное преобразование Фурье

Т.1. Пусть R - единицей. Тогда элемент w Rn если выполняются свойства:

1. w = 1;

2. wn = 1;

3. ]С wij =01 < i < n.

отображение, которое каждому вектору а = (ao, а1, , an-l) ai G R, О i n - ютствие вектор F(а) = 6 = (6o, 61, , 6n-1), где

6i Е ai wij, О < i < n - L

Обратное дискретное преобразование Фурье определяется как F-1(Ъ) = шаты вектора с равны

<п -

0 i и- 1.

То, что прямое и обратное дискретные преобразования Фурье взаимно обратны (т.е. F-1(F(a)) = a F(F-1(Ъ)) = Ъ), легко следует из определения примитивного корня.

/(x) = aixi i=o

ствует вычислению значений многочлена в точках w% 0 i и - 1, а обратное - интерполяции многочлена по его значениям в этих точках. То, что данные точки образуют циклическую мультипликативную подгруппу в R, позволяет построить быстрый алгоритм вычисления значения как прямого, так и обратного дискретного преобразования Фурье.

F( a)

ритм для вычисления F-1(Ъ) строится аналогично), называемый алгоритмом быстрого преобразования Фурье. Для простоты полагаем, что и = етачение многочлена /(x точке x = uji совпадает с остатком от деления многочлена /(x тогочлен x - u), 0 < i < и - многочлены x - lo\ 0 < i < и -1 попарно взаимно

xn - 1

подход, который рассматривался в п. 5.2 при нахождении значений остатков от деления элемента на взаимно простые модули. Заметим, что uin/2 = -1, поэтому

xxn - 1= {xnl2 - 1){xnl2 - ujnl2).

Далее

xnl2 - 1= {xnl4 - 1){xnl4 - ujn/2),

x.n/2

nl2 = lxn/4

x - U = - u

n/ {xn/4 - u3n/4)

Продолжаем этот процесс до получения линейных сомножителей x - ui. Таким образом, нахождение остатков от деления многочлена /(xa x - uj\ 0 i и - 1, можно провести с использованием

/(x)

n/2 1

rn/2 - ,.,n/2.

затем каждый из двух полученных n/4 - ujjn/4, и так далее.

Лемма. Пусть

/(x) = aixi

и с G ок от деления /(x) на (xn/2 - с) равен

Доказательство вытекает из равенства

/(x) = (x

= ( xn/2

-с) а+Ж+ г(ж). i=o

□

Из этой леммы вытекает, что для вычисления вектора коэффициентов остатка надо разделить вектор коэффициентов многочлена /(x) с

ны и сложить их с коэффициентами первой половины вектора. Это требует выполнения не более та операций кольца R.

В результате получаем, что для выполнения всего алгоритма надо выполнить не более

... + 2k

= ku

арифметических операций кольца R, т. е. сложность алгоритма быстрого преобразования Фурье равна O(ulog и).

Т.З. Благодаря алгоритму быстрого преобразования Фурье дискретное преобразование Фурье является очень удобным инструментом при проведении вычислений с многочленами. Так, например, с его помощью можно вычислять произведение многочленов со сложностью O(u log и) (выполнив сначала преобразование Фурье и получив значения многочленов в точках, затем перемножив полученные значения и, наконец, вернуться к коэффициентам многочлена с помощью обратного преобразования Фурье). Однако, оно обладает тем недостатком, что для существования преобразования Фурье над кольцом R требуется выполнение двух условий: существования примитивного корня степени тости числа отьце R, а эти условия