Глава 5. Битовая сложность

является невозрастающей конечной последовательностью натураль­ных чисел, и в силу предложения 9.1 никакое значение не встречается в ней более двух раз. Так как деление с остатком a_i__г на a_i требует не менее А(a_i) битовых операций, то общее число битовых опера­ций не может быть меньше, чем 1+ 1+ 2 + 2 + ...+ k + k = k(.k + 1) при k= [ⁿ^\ и n = n(loga₀). Следовательно, общее число битовых

операций есть ft(log²a₀).

Вместе с ранее установленной оценкой O(log²a₀) это дает оценку в (log² a₀). Теорема 4.2 из § 4 приводит нас к оценке в(m²) для бито­вой сложности алгоритма Евклида при избрании битовой длины m числа a₀ в качестве размера входа. Итак:

Если алгоритм Евклида основывается на некотором алгоритме де­ления с остатком, битовые затраты которого применительно к де­лимому v и делителю w допускают верхнюю оценку O (log v log w), то при рассмотрении большего входного числа a₀ в качестве разме­ра входа битовая сложность алгоритма Евклида допускает оценку 6(log² a₀). При рассмотрении m = А(a₀) в качестве размера входа име­ем оценку в(m²).

Оказывается, что полученные оценки сохраняют силу и при рас­смотрении расширенного алгоритма Евклида (пример 9.1)—обсто­ятельство, имеющее большое значение для модулярной арифметики (§ 22).

Предложение 21.3. Пусть расширенный алгоритм Евклида осно­вывается на некоторых алгоритмах деления с остатком и умноже­ния, битовые затраты каждого из которых применительно к целым v иw допускают верхнюю оценку O(logvlogw). Тогда, при рассмот­рении большего входного числа a₀ в качестве размера входа, бито­вая сложность расширенного алгоритма Евклида допускает оценку e(log²a₀), а при рассмотрении битовой длины m большего числа a₀ в качестве размера входа —оценку в(m²).

Доказательство. Исходя из вычислительных формул (9.8) и при­ нимая во внимание (9.12), (9.13), мы заключаем, что битовые за­ траты, дополнительные к затратам собственно алгоритма Евкли­ да («нерасширенного») на вычисление s_n, t_n, допускают оценку O(loga₀loga_i)—это обосновывается так же, как оценка (21.3). По­ этому сложность добавочной части расширенного алгоритма Евкли­ да допускает оценку O(log²a₀) и, в силу теоремы 4.2, оценку O{m²). Остается заметить, что, например, в(m²) + O{m²) = в(m²). □

§ 22. Модулярная арифметика

145

§ 22. Модулярная арифметика

Многие арифметические алгоритмы основываются на вычислениях по некоторому целому модулю k, или, как говорят, на модулярных вычислениях; соответственно, говорят о модулярной арифметике. Да­лее в этом параграфе мы считаем k фиксированным целым положи­тельным числом.

Целые a и b называют сравнимыми по модулю k и пишут

a ≡ b (mod k), (22.1)

если k | (a - b), т. е. если k является делителем разности a - b. Соот­ношение вида (22.1) называется сравнением. Изложение основ теории сравнений можно найти в любом учебнике алгебры¹. Мы приведем основные элементарные факты этой теории, не останавливаясь на их доказательстве:

(i) бинарное отношение сравнимости по модулю k является от­ношением эквивалентности на множестве целых чисел Z; (ii) если

a_г ≡ b_г (mod k) и a₂ ≡ b₂ (mod k), то

a_г±a₂ ≡ b_г± b₂ (mod k) и a_гa₂ ≡ b_гb₂ (mod k);

(iii) каждое целое число a сравнимо по модулю k в точности с од­ним целым числом из множества {О,1,..., k - 1}.

В силу (i) множество Z разбивается на классы эквивалентности по модулю k (кратко: классы по модулю k), и, согласно (ii), эти классы образуют кольцо, если считать, что сумма двух классов — это класс, содержащий сумму каких-либо чисел, взятых по одному из склады­ваемых классов, а произведение — это, соответственно, класс, содер­жащий произведение каких-либо чисел, взятых по одному из пере­множаемых классов. Нулем этого кольца является класс, содержащий число 0. Для введенного кольца используется обозначение Z_k, его на­зывают кольцом вычетов по модулю k (вычет—это в данном случае другое название класса эквивалентности по модулю k).

Любое множество {a₀, a_ъ ■■■,a_k-₁} чисел, взятых по одному из каж­дого класса по модулю k, называется полной системой представите­лей по модулю k.

Множество

I_k = {0,1, ...k-1},

См., например, [14, § 42, 43] и [22, гл. 4, § 4, п. 2].

146