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

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

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 102 103 104 105 106 107 < 108 > 109 110 111 112 113 114 .. 125 >> Следующая


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)).
Предыдущая << 1 .. 102 103 104 105 106 107 < 108 > 109 110 111 112 113 114 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed