Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
7. a) (BAD)i6. б) Никакого деления не требуется. Например, при переходе от двоичной к шестнадцатиричной системе просто разбиваем число (начав справа) на блоки по четыре разряда и рассматриваем каждую четверку как шестнадцатиричное число (или заменяем на один из символов 0-9, A-F).
8. 1) Посмотреть на верхний и нижний биты и проверить, не занималась ли единица для вычитания в младшем разряде. 2) Если биты одинаковы и единица не занималась или если верхние бит — это 1, а нижний — это 0 и единица занималась, то пишем 0 и идем дальше. 3) Если верхний бит — это 1, а нижний — это 0 и единица не занималась, то пишем 1 и идем дальше. 4) Если верхний бит — это 0, а нижний — это 1 и единица занималась, то занимаем единицу в старшем разряде, в текущий разряд разности помещаем 0 и идем дальше. 5) Если оба бита одинаковы и единица занималась или сверху стоит 0, а снизу 1 и единица не занималась, то занимаем единицу в старшем разряде, в текущий разряд разности помещаем 1 и идем дальше.
9. а) Требуется п — 1 умножений; в каждом из них промежуточное произведение 3J имеет не более 0(п) разрядов и 3 имеет 2 разряда, поэтому требуется 0(п) двоичных операций. Таким образом, в итоге получаем 0(га2). б) Здесь промежуточное произведение имеет O(ralogra) разрядов. Поэтому каждое произведение требует 0(ralog2 га) двоичных операций. Общая трудоемкость составляет 0(п2 log2 га) двоичных операций.
10. 0{п2 log2 JV).
11. a) 0(nlog2n). б) 0(log2n).
12. 0(rsra(log2 m + log га)).
13. а) Произведение 0(ra/logra) чисел из O(logra) разрядов каждое состоит 0(га/ log га) ¦ 0(log га) = 0(п) разрядов, б) 0(п log га). в)0(га2).
14. a) 0(v^nlog2 га), б) O(Vnlogn).
15. 0(т log га).
16. Предположим, что п состоит из к+1 бит. В качестве первого приближения для т = [у/п\ возьмем единицу с [к/2] нулями за ней. Находим знаки разрядов числа т, сдвигаясь от единицы слева направо и поочередно пробуя заменить 0 на 1. Если при этой замене квадрат полученного числа т становится больше га, то в этом разряде оставляем 0.
228
ОТВЕТЫ К УПРАЖНЕНИЯМ
§1.2
1. б) Простой контрпример: пусть 6 = —а.
2. 16 делителей: 1, 3, 5, 7, 9, 15, 21, 27, 35, 45, 63, 105, 135, 189, 315, 945.
3. а) Если а\п, то пишем п = ab и полагаем а <-> Ь. б) Имея п = ab, где
а > Ь, полагаем s = (а + Ь)/2 и t = (а — 6)/2. Обратно, имея п = s2 — і2, положим a = s + t, b = s - t. в) 4732 - 4722, 1592 - 1562, 972 - 922, 712 - 642, 572 - 482, 392 - 242, ЗЗ2 - 122, 312 - 42.
4. 6) = 100! = 297 -З48 • 524 • 716 ¦ II9 • 137 ¦ 175 • 195 • 234 ¦ 293 •3I3 ¦ 372 •4I2 ¦ 432 • 472 ¦ 53 • 59 • 61 • 67 ¦ 71 • 73 • 79 • 83 ¦ 89 ¦ 97. в) Формула имеет вид (n - 5p(n))/(p - 1). Чтобы доказать это, запишем п = djt-iP*-1 4-- ¦ - + dip + do и заметим, что \njp'\ = djfc-ip*-1 ~; + ¦ ¦ ¦ + rfj' + iP + dj для каждого j. Далее воспользуемся формулой из пункта а).
6. а) 1 = 11 • 19 - 8 • 26. б) 17 = 1 • 187 - 5 • 34. в) 1 = 205 ¦ 160 - 39 • 841. г) 13 = 65 ¦ 2171 - 54 ¦ 2613.
7. Для примера сравниваем два способа в случае г):
2613
= 2171 4- 442
2613
= 2172 + 442
2171
= 4 • 442 + 403
2171
= 5-442 - 39
442
= 403 + 39
442
= 11-39 + 13
403
= 10-39 + 13
39
= 3 13
39
= 3 13
8. б)
НОД (101000110101, 100001111011) = НОД (110111010, 100001111011)
= НОД (11011101, 100001111011) = НОД (11011101, 11110011110) = НОД (11011101,1111001111) = НОД (11011101, 1011110010)
= нод (11011101,101111001) = нод (11011101, iooiiioo)4^-—у
= НОД (11011101,100111) = НОД (10110110, 100111) = НОД (1011011, 100111) = НОД (110100, 100111) = НОД (1101, 100111) = НОД (1101, 11010) = НОД (1101, 1101) = 1101.
в) Рассмотреть произведение ab и показать, что через каждые два шага произведение двух чисел, для которых вычисляется наибольший общий делитель, уменьшается, по крайней мере, в два раза. Таким образом, потребуется 0(log а) шагов. Каждый шаг — это не более чем вычитание, требующее O(loga) двоичных операций (заметим, что ни делений, ни умножений алгоритм не содержит), г) Этот алгоритм не позволяет выразить НОД в виде целочисленной линейной комбинации двух исходных чисел. Однако его можно модифицировать так, что это будет возможным, см. статью G.H.Norton «Extending the binary GCD algorithm* в книге Algebraic Algorithms and Error Correcting Codes. Heidelberg etc.: Springer, 1986, c. 363-372.
ОТВЕТЫ К УПРАЖНЕНИЯМ
229
9. 0(log a log 6 + log3 b).
10. а) Остаток уменьшается медленнее всего, когда все частные равны единице, б) Пишем (J J) = ВАВ~1, где А = (°Q0,) — диагональная матрица из собственных значений, а столбцы матрицы В являются собственными векторами, т.е. B= (?°). в) Так как уДа > s/Efk+2 = ак+2 - а,к+2 > ак+2 - 1, то к < (log(l 4- \/5a))/(log а) — 2. Можно также получить более простую оценку к < (log a)/(log а). Последняя равна 1,44042... ¦ log2 а, в то время как оценка из доказательства предложения 1.2. 1 равна 2log2a.
11. б) К сумме величин (logr,)(l + log <7;+1) применить неравенства г,- ^ 6 и ГІ9і+і ^ а- Вывести, что эта сумма ограничена величиной 0((log 6)(log a + log a)).