Теперь возведение в данную степень можно свести к последовательно-

в квадрат. Отсюда получается следующая оценка сложности O(M(log N) log а) = O(M(n)fc).

§ 3. Сложность алгоритма Евклида

3.1. Обычный алгоритм Евклида. Будем обозначать наибольший общий делитель чисел и ез Напомним, что алгоритм

Евклида заключается в последовательном выполнении операции деления с остатком до получения нулевого остатка. Пусть A>B>0. Обозначим A=r b B=ri-2 = diVi-i щи «=1,..., rfc i = dfc+1 r. Тогда (A, B) = тения остатка rk+1 = 0 необходимо выполнить fc+1 деление.

Оценим число делений, выполняемое в алгоритме Евклида. Для этого рассмотрим последовательность чисел Фибоначчи /о ... ,Л,..., где /о = О, Л = 1, Л = Л 1 + Л 2, fc 2.

Лемма. При к>1 справедливо неравенство fkR, яде R=

Доказательство. Применим индукцию по ри fc=2 утверждение очевидно.

Далее, используя предположение индукции, имеем

/к+1 = /к + /к-1 > Rk-2 + Rk-3 = Rk-3 (R + 1) = Rk-3 R2 = Rk

так как мым корнем уравнения ж2 = x + L □

N> О

делений в алгоритме Евклида для нахождения наибольшего общего делителя чисел и B О <B<A < тсхо дит 1 + [logR NJ.

Доказательство. Докажем, что /i <rk+1- щи «=1,..., k+2. При « = то. Для « + 1, в силу предположения индукции, имеем

rk-i = dk-i+2rk-i+1 + rk-i+2 rk-i+1 + rk-i+2 /i + =

Поэтому, A r-1 /k+2 Rk, откуда получается искомая оценка числа делений k + 1 < 1 + [logR □

Непосредственно из этой теоремы можно получить оценку сложности алгоритма Евклида для нахождения наибольшего общего дели-n

O(M(n)(k + 1)) = O(M(n) logn) < O(n2 logn).

Вместе с тем, эту оценку можно уточнить, если заметить, что сложность операции деления углом числа число B О < B < A, на самом деле имеет вид O(logA(logA - logB + 1)). Отсюда, обозначая через отси остатка « = -1,0,1,...,k, получаем более точную оценку сложности алгоритма Евклида kk O(ni(ni-1 - ni + 1)) VO(no(ni-1 - ni + 1)) =

= (ni-1 - ni + 1)

= O(no(n-1 - nk + k + 1)) =

= O(non-1) = O(log A • logB) = O(n2).

3.2. Другие алгоритмы. Оценка сложности алгоритма Евклида не является оптимальной для задачи нахождения наибольшего общего делителя.

Имеется множество различных модификаций алгоритма Евклида. Можно, например, уменьшить число шагов алгоритма, модифицируя алгоритм с целью уменьшения абсолютных значений остатков. А именно, будем заменять остаток г» на г\-г\1, если Vi-Y. При таком исправлении получается последовательность чисел, удовлетворяющая условию \г\ \ < -y- То, что при этом некоторые из чисел будут отрицательными, не влияет на вид общих делителей. В результате получается оценка числа делений k + 1 < 1 + [log2 ртчем R =1,618... < 2. Однако, данный подход не улучшает общую оценку сложности модифицированного алгоритма Евклида O(M(logN) logN) = O(M(n)n), где n = log N - таписи чисел и B.

Существуют алгоритмы, в которых вообще не выполняется операция деления. Например, в алгоритме LSGCD (left shift greatest common divisor) операция деления с остатком заменена на левый сдвиг делителя с последующим вычитанием из делимого, такой, что полученная последовательность на каждом шаге удовлетворяет условию из предыдущего алгоритма. В данном алгоритме выполняется O( n) O( n)

O( n2 )

Заметим, наконец, что имеется алгоритм нахождения наибольшего общего делителя с оценкой сложности O(M(log N) log log N) = = O(M(n) log n) приведено не будет (см. [2]).

3.3. Расширенный алгоритм Евклида. Рассмотрим теперь расширенный алгоритм Евклида, позволяющий наряду с наибольшим общим делителем чисел и альные числа и у, удовлетворяющие равенству Ax + By = (A,B). От обычного алгоритма Евклида он отличается тем, что наряду с последовательностью остатков отательные последовательности xj и у»:

r-i = A ro = B; x-i = 1, y-i = 0, xo = 0, yo = 1; for i = 0 mti I г» > 0 do begin

di = [ri-2/rj-i J; rj = ri-2 - dirj-i; xj = xi-2 - dixj-i; yi = yi-2 - diyi-i; i = i + 1;

xk yk rk = ( A, B)

силу следующего утверждения:

Лемма. Лри всех i, -1 <i < к, выполняется равенство

xj A + yi B = ri.

Доказательство. Применим индукцию по При i = -1,0 равенство очевидно. Если равенства доказаны для всех значений ин-

получаем

xj A + yjB = (xi-2 - di yi-i) A + (yi-2 - diyi-i)B =

= (xi-2 A + yi-2B) - di(xi-i A + yi-iB) = rj. □

Легко видеть, что сложность данного алгоритма отличается от сложности обычного алгоритма Евклида не более, чем на константный сомножитель, и составляет O(M(logN)logN) = O(M(и)и), где и = log N - таписи чисел и B.

§ 4. Сложность операций в кольце вычетов

Будем отождествлять элементы кольца вычетов Zn с числами в интервале 0 < A < Щсть и = \log2 N~\.

4.1. Сложение и вьгаитание. При сложении чисел в интервале 0 A, B < ма A + B может выйти за границы интервала, поэто-

A+B-N

A - B + N

O( и)

4.2. Умножение. Для нахождения вычета, соответствующего про-

2и и

этому, сложность данной операции равна O(M(и)).

Во многих случаях, особенно при аппаратной реализации алгоритмов, удобно отказаться от операций умножения и деления и заменить их операциями сложения. Один из таких алгоритмов, предложенный

ное число, требуется умножить вычеты A 2iaiii B. Рассмотрим

алгоритм R = 0;

for i = 0 шЬ I i < и do begin

if ai = 1en R = R + B;

if ho then R = R + N;

R = R/2;

if R en R = R - N.

Суть данного алгоритма в том, что в силу равенства

A 2iai = (... (2an-i + an-2)2 + ... ai)2

- ao

BA AB = aoB + 2(aiB + ... 2(an-2B + 2an-iB)...).

прибавление к текущему значению етения aiB i = 0,... ,и - 1, с последующим делением на 2. Благодаря этому делению полученные значения всегда находятся в интервале 0 < R < N. В результате работы данного алгоритма получается число 2-nAB mod N. Теперь для получения числа AB mod N необходимо применить еще один раз

данный алгоритм к числам 22n mod и 2-nAB mod N. Поскольку число 22n mod N вычисляется с помощью сдвигов и вычитаний со O( n2 )

нее и хранить полученное значение), а алгоритм также выполняется O( n2 )

O( n2 )

4.3. Обращение. Для заданного числа Д 0<A<N, находим с помощью расширенного алгоритма Евклида числа и у, удовлетворяющие равенству xA + yN = (A, N&ли (A, N) > о A не имеет обратного.

( A, N) = 1 x mod N

Таким образом, обращение в кольце вычетов можно выполнить за O(M(n)n)

4.4. Деление. Так как А/В = Aj, то деление в кольце вычетов

O(M(n)n)

§ 5. Использование модульной арифметики

5.1. При вычислениях с целыми числами часто применяется следующий прием. Если известно, что исходные числа и результаты вы-

неравенства двух видов О N < ши -M/2 < N < M/2), то вычисления можно производить в кольце вычетов Zm, отождествляя числа

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

Наиболее эффективным такой переход является в случае, когда M

стых чисел M=m1m2 ... mk, поскольку в этом случае можно воспользоваться изоморфизмом колец

Zm = Z„

При этом соответствии каждому числу тервала 0м<M соответствует набор («1 ,«2, ,ukвде Ui = u mod i = 1,..., k. (Здесь и далее запись u mod m, в отличие от записи правой части сравнения u (mod m)

исходными числами можно сначала перейти к их остаткам и производить все вычисления в кольцах i = 1, , k, а затем, получив результат, выполнить обратный переход и восстановить по остаткам искомое число.

( u1 , u2 , , uk ) u

k u mi i = 1 , , k mi

записываются с помощью таков, то число u записывается с помощью Сложность деления k6-6HTOBoro числа на те равна O(kM(6)), поэтому сложность перехода оценивается величиной O(k2M(6)).

Эту оценку можно улучшить, если применить технику «разделяй и властвуй» и разбить процесс вычислений на два этапа. Пусть для

k = 2*

тельно находятся произведения чисел

m1m2, mзm4,, mk-1 mk,

m1m2 mk/4, m3k/4+1 mk,

m1m2 mk/2, mk/2+1 mk

Ha втором этапе выполняются деления

U11 = u mod (m1m2 mk/2), U12 = u mod (mk/2+1 mk/2), U21 = u11 mod (m1m2 mk/4),, = mod (m3k/4+1 mk/2),

u*-1,1 = u*-2,1 mod (m1m2), u*-1,2 = u*-2,1 mod (m3m4), , u*-1,k/2 = u*-2,k/4 mod (mk-1 mk), u1 = u*-11 mod m1, u2 = u*-11 mod m2, uk = u*-1k/2 mod mk

Легко видеть, что для выполнения первого этапа требуется

2*-1M (6) + 2*-2M (26) + + 2M (2*-16) = O(tM (kb))

двоичных операций. На втором этапе требуется выполнить

2M (2*-16) + 22M (2*-26) + + 2*-1M (6) = O(tM (k6))

двоичных операций.

Таким образом, общая оценка сложности имеет вид O(M(k6) log k) двоичных операций.