Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Во-вторых, если мы хотим получить простую и удобную в работе оценку, мы всегда должны предполагать, что имеем дело с «самым плохим случаем». Например, если двоичное разложение числа т имеет много нулей, то /' будет значительно меньше /. Поэтому можно использовать оценку Time (умножение ^-разрядного и /-разрядного двоичных чисел)< /с-(число единиц в двоичном разложении т). Однако обычно вместо такого уточнения (понижения) нашей временной оценки удобнее пользоваться простой равномерной оценкой, зависящей лишь от длины записи п и т, а не от конкретных значений битов.
Как частный случай, имеем оценку:
Time (умножение двух /с-разрядных двоичных чисел) < к2.
Наконец, наша оценка kl может быть выражена в терминах пит, если вспомнить приведенную выше формулу для числа разрядов, из которой следует, что к = [log2 п] + 1 ^ j^-J + 1 и / = [log2 m] + 1 ^
6
ГЛ. I. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ЧИСЕЛ
Пример 6. Найти верхнюю границу для числа двоичных операций, необходимых для вычисления п!.
Решение. Используем следующую процедуру. Сначала умножим 2 на 3, затем результат умножим на 4, новый результат умножим на 5 и т. д., пока не получим ті!. На (j - 1)-м шаге (j = 2, 3,..., п - 1) производится умножение j\ на j + 1. Поэтому есть п — 2 шагов, каждый из которых состоит в умножении частичного произведения j\ на очередное целое число. Частичные произведения быстро станут очень большими. В качестве оценки для числа разрядов частичного произведения в наихудшем случае возьмем число разрядов последнего произведения, т.е. числа п!.
При определении числа двоичных разрядов в произведении мы используем тот факт, что это число не превосходит суммы числа разрядов у сомножителей (см. выше рассуждение об умножении). Следовательно, произведение п целых /с-разрядных чисел имеет не более пк разрядов. Таким образом, если п — двоичное /с-разрядное число (тогда любое меньшее число имеет не больше к разрядов), то ті! имеет самое большее пк разрядов.
Итак, в каждом из п — 2 умножений, необходимых при вычислении nl, мы умножаем не более чем /с-разрядное целое число j + 1 на не более чем ті/с-разрядное целое число jl. Это требует самое боль-шее пк двоичных операций. Всего таких умножений п — 2. Поэтому общее число двоичных операций ограничено величиной (ті — 2)пк =
2 2 2
п(п — 2)([log2 n] + 1) , что приблизительно равно n (log2 п) .
П р и м е р 7. Определить верхнюю границу для числа двоичных операций, необходимых для умножения многочлена ^a1X1 степени не выше пг на многочлен bjXJ степени не выше п2; коэффициенты многочленов — положительные целые числа, не превосходящие 771. Считается, что Tl2 ^ Tl1 .
Решение. Для вычисления выражения $Z,-+j_„ a^j, являющегося коэффициентом при xv в произведении многочленов (здесь О ^ V ^ Ti1 + Ti2), требуется не более Ti2 + 1 умножений и Ti2 сложений. Перемножаемые числа ограничены величиной т, а складываемые чи-
2
ела ограничены величиной т ; но, так как мы должны сложить Ti2 таких чисел, надо взять в качестве границы для слагаемых величи-ну Ti2TTi . Таким образом, необходимое для вычисления коэффициента при хУ число двоичных операций не превосходит
(Tl2 + I)(IOg2 771 -f I)2 + Tl2(IOg2(Tl2TTl2) + 1).
Поскольку в произведении многочленов имеется тії +п2 +1 степеней х",
§ 1. ВРЕМЕННЫЕ ОЦЕНКИ СЛОЖНОСТИ
7
наша временная оценка умножения многочленов выражается как
Пренебрегая единицами, получаем менее строгую, но более компактную оценку
Замечание. Положим п = пг ^ тг2, и пусть т ^ 16 и "і ^ у/Щ (что обычно выполняется на практике). Тогда последнее
2 2
выражение можно упростить до An (log2 m) . Этот пример показывает, что в общем случае нет единого «правильного ответа» на вопрос о нахождении границы для времени решения задачи. Можно искать границу как достаточно простую функцию от исходных данных (в рассмотренном случае это Ti1, п2 и т), которая для большинства исходных данных дает оценку, по порядку более или менее близкую к числу реально выполняемых двоичных операций. Поэтому, скажем, в примере 7 нет смысла заменять нашу оценку оценкой An тп, так как при больших тп она на много порядков больше реального числа операций.
До сих пор мы имели дело со сложением и умножением целых чисел. Две другие арифметические операции — вычитание и деление — имеют те же самые оценки временной сложности, что сложение и умножение соответственно: Time (вычитание /с-разрядного двоичного числа из /-разрядного) ^ max (A;,/), Time (деление /с-разрядного двоичного числа на /-разрядное) ^ kl. Более точно, для описания вычитания надо расширить круг двоичных операций, включив в него операцию вычитания нуля или единицы из других нуля или единицы, возможно, с займом единицы из старшего разряда (см. пример 8).
Анализируя деление в двоичной системе, будем ориентироваться на иллюстрацию, подобную примеру 3. Пусть к ^ I (если к < I, деление тривиально, т. е. частное равно нулю, а все делимое образует остаток). Нахождение частного и остатка требует самое большее к — I + 1 вычитаний. Каждое вычитание требует / или / + 1 двоичных операций, но в последнем случае в самом левом разряде разности будет стоять нуль, поэтому можно опустить одну двоичную операцию (считая, что это скорее операция «по учету данных», а не вычисление). Подобным образом мы игнорируем и другие технические детали, например, сравнение двоичных целых чисел (при определении минимального числа разрядов делимого, которые образуют число, большее
