Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 30
Текст из файла (страница 30)
Это дает нам оценку сверху3c(log2 a1 )(3 log2 a1 + log2 a0 )для числа битовых операций при a1 > 1. Учитывая, что a0 ¾ a1 , мыполучаем отсюда следующее.Количество битовых операций, затрачиваемых при примененииалгоритма Евклида к a0 , a1 , допускает оценкуO(log a0 log a1 )(.)и оценки O(log2 a0 ), O(m2 ), m = λ(a0 ).Приведенные оценки получены в предположении, что для построения остатков используется наивное деление, имеющее квадратичнуюсложность.
Может ли быть так, что привлечение имеющего меньшуюбитовую сложность алгоритма деления с остатком приведет к существенно меньшим битовым затратам алгоритма Евклида? Ответ отрицательный: нетрудно, например, показать, что если a0 берется в качестве размера входа, то для битовой сложности алгоритма Евклидавыполняется оценка Ω(log2 a0 ).В самом деле, в примере . было показано, что для каждого a0 можно подобрать меньшее его a1 такое, что для числа деленийс остатком выполняется неравенство (.).
Если обозначить это число делений через n, то будем иметь n = Ω(log a0 ), при этомλ(a0 ), λ(a1 ), ..., λ(an )Глава . Битовая сложностьявляется невозрастающей конечной последовательностью натуральных чисел, и в силу предложения . никакое значение не встречаетсяв ней более двух раз. Так как деление с остатком ai−1 на ai требуетне менее λ(ai ) битовых операций, то общее число битовых операций не jможетkбыть меньше, чем 1 + 1 + 2 + 2 + ...
+ k + k = k(k + 1)n+1и n = Ω(log a0 ). Следовательно, общее число битовыхпри k =2операций есть Ω(log2 a0 ).Вместе с ранее установленной оценкой O(log2 a0 ) это дает оценкуΘ(log2 a0 ). Теорема . из § приводит нас к оценке Θ(m2 ) для битовой сложности алгоритма Евклида при избрании битовой длины mчисла a0 в качестве размера входа. Итак:Если алгоритм Евклида основывается на некотором алгоритме деления с остатком, битовые затраты которого применительно к делимому v и делителю w допускают верхнюю оценку O(log v log w),то при рассмотрении большего входного числа a0 в качестве размера входа битовая сложность алгоритма Евклида допускает оценкуΘ(log2 a0 ).
При рассмотрении m = λ(a0 ) в качестве размера входа имеем оценку Θ(m2 ).Оказывается, что полученные оценки сохраняют силу и при рассмотрении расширенного алгоритма Евклида (пример .) — обстоятельство, имеющее большое значение для модулярной арифметики(§ ).Предложение .. Пусть расширенный алгоритм Евклида основывается на некоторых алгоритмах деления с остатком и умножения, битовые затраты каждого из которых применительно к целымv и w допускают верхнюю оценку O(log v log w). Тогда, при рассмотрении большего входного числа a0 в качестве размера входа, битовая сложность расширенного алгоритма Евклида допускает оценкуΘ(log2 a0 ), а при рассмотрении битовой длины m большего числа a0в качестве размера входа — оценку Θ(m2 ).Доказательство.
Исходя из вычислительных формул (.) и принимая во внимание (.), (.), мы заключаем, что битовые затраты, дополнительные к затратам собственно алгоритма Евклида («нерасширенного») на вычисление sn , tn , допускают оценкуO(log a0 log a1 ) — это обосновывается так же, как оценка (.). Поэтому сложность добавочной части расширенного алгоритма Евклида допускает оценку O(log2 a0 ) и, в силу теоремы ., оценку O(m2 ).Остается заметить, что, например, Θ(m2 ) + O(m2 ) = Θ(m2 ).§ . Модулярная арифметика§ . Модулярная арифметикаМногие арифметические алгоритмы основываются на вычисленияхпо некоторому целому модулю k, или, как говорят, на модулярныхвычислениях; соответственно, говорят о модулярной арифметике. Далее в этом параграфе мы считаем k фиксированным целым положительным числом.Целые a и b называют сравнимыми по модулю k и пишутa ≡ b (mod k),(.)если k | (a − b), т.
е. если k является делителем разности a − b. Соотношение вида (.) называется сравнением. Изложение основ теориисравнений можно найти в любом учебнике алгебры . Мы приведемосновные элементарные факты этой теории, не останавливаясь на ихдоказательстве:(i) бинарное отношение сравнимости по модулю k является отношением эквивалентности на множестве целых чисел Z;(ii) еслиa1 ≡ b1 (mod k) и a2 ≡ b2 (mod k),тоa1 ± a2 ≡ b1 ± b2 (mod k) и a1 a2 ≡ b1 b2 (mod k);(iii) каждое целое число a сравнимо по модулю k в точности с одним целым числом из множества {0, 1, ..., k − 1}.В силу (i) множество Z разбивается на классы эквивалентности помодулю k (кратко: классы по модулю k), и, согласно (ii), эти классыобразуют кольцо, если считать, что сумма двух классов — это класс,содержащий сумму каких-либо чисел, взятых по одному из складываемых классов, а произведение — это, соответственно, класс, содержащий произведение каких-либо чисел, взятых по одному из перемножаемых классов.
Нулем этого кольца является класс, содержащийчисло 0. Для введенного кольца используется обозначение Zk , его называют кольцом вычетов по модулю k (вычет — это в данном случаедругое название класса эквивалентности по модулю k).Любое множество {a0 , a1 , ..., ak−1 } чисел, взятых по одному из каждого класса по модулю k, называется полной системой представителей по модулю k.МножествоIk = {0, 1, ..., k − 1},См., например, [, § , ] и [, гл. , § , п. ].Глава .
Битовая сложностьуказанное в (iii), называется канонической (или начальной) полнойсистемой представителей по модулю k. Иногда используется и симметричная полная система представителей:mj konlk−k + 1, ..., −1, 0, 1, ...,,Sk =22которая является симметричной (при условии игнорирования знаков) только при нечетном k: например, S3 = {−1, 0, 1} и S4 == {−1, 0, 1, 2}.Пусть для изображения элементов кольца Zk используется система Ik . Операциям сложения и умножения в Zk соответствуют обычные сложение и умножение в Z с последующей заменой полученногорезультата остатком от его деления на k.
Если некоторому элементу кольца Zk соответствует число a системы Ik , то противоположному (обратному по сложению) элементу будет соответствовать числоk − a, если a 6= 0, и число 0, если a = 0.Исследуем битовую сложность операций в кольце Zk . Будем считать размером входа битовую длину m числа k и ограничимся верхними асимптотическими оценками.
Для операций сложения и нахождения противоположной величины имеем, очевидно, оценку O(m). Использование операции наивного умножения целых чисел приводитк оценке O(m2 ) для сложности умножения в Zk . Эта оценка, разумеется, сохраняется и при использовании более быстрого умноженияи деления в Z.Как известно, в случае простого k кольцо Zk является полем. Присоставном k это кольцо полем не является и, более того, содержит делители нуля: если k = pq, p > 1, q > 1, то произведение элементов Zk ,изображаемых числами p, q ∈ Ik , равно нулю.
Допустим, что k является простым и примем для этого простого числа обозначение p,по-прежнему считая его битовую длину равной m. Нахождение обратного к элементу кольца Z p , представленному целым ненулевымчислом a ∈ I p , может быть выполнено с помощью расширенного алгоритма Евклида. Так как p и a, очевидно, взаимно просты, то c помощью расширенного алгоритма Евклида можно найти s и t такие, чтоsp + ta = 1. Получаем ta ≡ 1 (mod p), т.
е. обратным к классу, содержащему a, является класс, содержащий t. В силу (.) имеем | t | < p;если t < 0, то заменяем t на t + p (напомним, что мы используемэлементы системы I p для изображения элементов поля Z p ).Пример .. Для p = 13, a = 5 получаем с помощью расширенногоалгоритма Евклида 2 · 13 + (−5) · 5 = 1, и отсюда 8 = −5 + 13 являетсяобратным для 5 в Z13 (проверка подтверждает это: 5 · 8 ≡ 1 (mod 13)).§ . Модулярная арифметикаКак следствие предложения . получаем такое утверждение.Предложение ..
Пусть расширенный алгоритм Евклида основывается на некоторых алгоритмах деления с остатком и умножения, битовые затраты каждого из которых применительно к целымv и w допускают оценку O(log v log w). Тогда битовая сложность обращения в поле Z p с помощью расширенного алгоритма Евклида допускает оценку O(log2 p) при использовании числа p в качестве размеравхода и, соответственно, оценку O(m2 ) при использовании в этомкачестве битовой длины m числа p.Несомненным достоинством алгоритма обращения, основанногона расширенном алгоритме Евклида, состоит в том, что с его помощью обращение возможно всякий раз, когда обращаемое число и модуль взаимно просты, а не только тогда, когда модуль — простое число. Например, можно определить a такое, что 5a ≡ 1 (mod 6) — средичисел, входящих в I6 , значением a является 5.