Научная литература
booksshare.net -> Добавить материал -> Математика -> Коблиц Н. -> "Курс теории чисел и криптографии" -> 8

Курс теории чисел и криптографии - Коблиц Н.

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 2 3 4 5 6 7 < 8 > 9 10 11 12 13 14 .. 125 >> Следующая


В общем случае, когда оценивается число двоичных операций, требующихся для решения какой-либо задачи, сначала надо определить и выписать подробную процедуру решения задачи. Конкретная пошаговая процедура выполнения вычислений называется алгоритмом. Конечно, может существовать много разных алгоритмов, выполняющих одну и ту же работу. Можно воспользоваться тем из них, который попроще в записи, или тем, который быстрее работает, или выбрать какой-то компромисс между простотой и быстродействием. Использованный выше алгоритм умножения п на т далек от самого быстрого из известных. Но вместе с этим он много быстрее метода повторного сложения (m-кратного сложения числа п с собой).

Пример 10. Оценить время, требующееся для перевода числа из к бит в десятичную систему счисления.

Решение. Пусть п — целое из к бит, записанное в двоичной системе счисления. Алгоритм перевода следующий. Разделим п на 10 = (101O)2- Остаток от деления — который является одним из чисел 0, 1, 10, 11, 100, 101, ПО, 111, 1000 или 1001 — даст содержимое d0 разряда единиц. Частное от деления возьмем вместо п, поделим на (101O)2 и возьмем остаток от этого деления в качестве d1, а частное — в качестве делимого при следующем делении на (101O)2-Это процесс должен повторяться столько раз, сколько десятичных

разрядов содержится в числе тг, т.е.

+ 1 = 0(к) раз. То-

гда процесс будет завершен. (Наши записи мы могли вести и в десятичной системе, используя более привычные обозначения для остатков 0,1,2,3,...,9 вместо 0,1,10,11,...,1001.) Как много двоичных операций будет сделано? Мы сделали 0(к) делений, каждое из них требовало 0(4A;) операций (делимое содержит не более к бит, а де-

§ 1. ВРЕМЕННЫЕ ОЦЕНКИ СЛОЖНОСТИ

11

литель (101O)2 — 4 бита). Но 0(Ak) эквивалентно 0(к) (постоянный множитель несуществен в обозначении О-большое). Поэтому общее число двоичных операций равно 0(к) ¦ 0(к) = 0(к2). Если желательно выразить оценку в терминах п, а не к, то, используя равенство к = O(logn), можно записать

Time (перевод п в десятичную систему счисления) — 0(log Tl).

Пример 11. Оценить время, требующееся для перевода числа ті из к бит в систему счисления по основанию Ь, которое может быть очень большим.

Решение. Используя алгоритм примера 10 (только делим теперь на число b из / бит), получаем, что каждое деление выполняется дольше (если / велико) и требует О (kl) двоичных операций. А сколько раз придется делить? Следует заметить, что число разрядов при записи ті в 6-ичной системе равно 0(к/1) (см. пример 9(c)). Поэтому общее число двоичных операций во всех делениях равно 0(k/l)-0(kl) = О (к ). Это тот же ответ, что и в примере 10. Значит, наша оценка для времени перевода числа в новую систему счисления не зависит от основания системы (сколь бы большим оно ни было). Это так, поскольку увеличение времени для определения содержимого каждого разряда компенсируется уменьшением числа этих разрядов.

Пример 12. Выразить при помощи О-большого время, требующееся для вычисления а) п\, Ъ) (™) (см. примеры 6 и 8).

Решение, а) 0(п2 log2 п), Ъ) 0(т2 log2 п).

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

Определение. Алгоритм для проведения вычислений, определяющихся целыми числами Ti1, п2,..., Tir из ki, к2, ¦ ¦ ¦, кг бит, соответственно, называется полиномиальным по времени алгоритмом, если существуют такие целые числа ^1, d2, ¦ ¦ ., dr, что число двоичных операций при работе этого алгоритма равно О (kdlk22 ¦ ¦ -kdr).

Таким образом, обычные арифметические операции +, -, X, -f-дают примеры полиномиальных по времени алгоритмов. Еще один пример — перевод чисел из одной системы счисления в другую. С другой стороны, вычисление тг! не является такой операцией. (Однако, если требуется найти лишь заданное число значащих цифр, например, первые 1000 двоичных разрядов, то можно найти ті! за полиномиальное время при помощи формулы Стирлинга.)

12

ГЛ. I. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ЧИСЕЛ

УПРАЖНЕНИЯ

1. Умножить (212)з на (122)3.

2. Разделить (40122)7 на (126)7.

3. Перемножить двоичные числа 101101 и 11001 и разделить 10011001 на 1011.

4. В системе счисления по основанию 26, представляя 0-25 буквами A-Z: а) умножить YES на NO, б) разделить JQVXHJ на WE.

5. Записать число е = 2,7182818... а) в двоичной системе счисления (с 15 знаками после запятой), б) по основанию 26 (с 3 знаками после запятой).

6. Под чисто периодической дробью с периодом / в 6-ичной системе понимается число между 0 и 1, в 6-ичной записи которого после запятой стоит периодическая последовательность периода. /. Например, в десятичной системе счисления 1/3 — чисто периодическая дробь с периодом 1, а 1/7 — чисто периодическая дробь с периодом 6. Доказать, что несократимая дробь c/d между 0 и 1 является чисто периодической с периодом / в 6-ичной системе тогда и только тогда, когда 6-^ — 1 есть кратное числа d.

7. а) В шестнадцатиричной системе с 6 — 16 буквы A-F изображают цифры от 10 до 15, соответственно. Разделить (іЗІВбСЗ)іб на (lA2F)i6.
Предыдущая << 1 .. 2 3 4 5 6 7 < 8 > 9 10 11 12 13 14 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed