Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
8. а) (1 - 2-")(1 - 2-n + 1)---(l -2-"+*-1). б) 0,298.
9. Выражение в оценке сложности ро-метода становится в 3,2•1O12 раз больше, в оценке сложности метода факторных раз в 2,6 • 10е раз больше.
10. а) Если s < so, то h(s) ^ f(s) > /(so) = ^h(so), а если s > so, то h(s) ^ g(s) > g(so) = ^h(so)- б) Применить часть а) к log/(s) и logg(s).
§ V.4
1 »4J-J-J- Rl J-J- J-J-J-J-J-J-J- „11 J-J-J-J-I ' 1+1+44- 1+1+1+1+1+1+1+1+1 + 1- 7+ 1+ 2+ 4
2. а) Так как z = a + ^•, то число x должно быть положительным корнем уравнения г2 — ах — 1 = 0, т. е. х = (a + у'а2 + 4)/2. б) Так как все числа а,- равны 1, то рекуррентное соотношение для числителей и знаменателей приближений то же самое, что и для чисел Фибоначчи.
3. 2 + г^^тЗрї^4^Т+Г+"б'''' можно показать, что а,- при і = 2 (mod 3) — последовательные четные числа и а,- = 1 для всех остальных г.
4. Для каждого 4,- разность 42 — с2п есть наименьший абсолютный вычет 6? по модулю п. Если р делит его, то 6? s с2п (mod р). Но отсюда следует, что п — квадратичный вычет по модулю р.
5. Следующие ниже таблицы составлены для стольких первых значений г, что наименьшие абсолютные вычеты б2,..., Ъ2 обеспечивают факторизацию п. В четырех случаях (пп. ж), з), к), л)) существуют меньшие значения г, при которых можно найти такие подмножества вычетов, что сумма соответствующих им векторов є,- равна нулю; однако в этих случаях мы приходим к сравнениям Ь = ±с (mod тг).
а)
г
а і bi
bf (mod п)
В = { — 1,2, 5,11}, 6 = 97 - 195 ¦ 3413, с = 22 • 5 • 11, НОД (4 + с, тг) = 257.
б)
і 0 12 3
а; 116 2 4 1
4,- 116 233 1048 1281
Ь? (mod п) -105 45 -137 80
В = {2, 3, 5}, 4 = 233 • 1281, с = 22 • 3 • 5, НОД (Ь + с, n) = 191.
0
1
2
3
97
1
1
17
97
98
195
3413
-100
95
-11
44
г
0
1
2
а і
93
1
2
bi
93
94
281
(mod п)
-128
59
-32
В = {-1,2}, 4 = 93 • 281,с = 2б,НОД (4 + c,n) = 67.
248
ОТВЕТЫ К УПРАЖНЕНИЯМ
г)
i 0 12 а,- 120 8 3
ii 120 961 3003 Ь? (mod п) -29 65 -116
В = {-1, 2, 29}, Ь = 120 • 3003, с = 2 • 29, НОД (b + с, n) = 307.
Д)
г 0 1 2 3 4 5 6
а; 111 2 1 2 2 7 1
6,- 111 223 334 891 2116 3300 5416
6? (mod п) -82 117 -71 89 -27 116 -39
5=(-1,3, 13}, Ъ = 233 • 2116 • 5416,с = З3 • 13, НОД (Ь + с, n) = 157.
е)
і 0 1 2 3 4 5
а, 120 1 1 8 2 2
ft; 120 121 241 2049 4339 10727
62 (mod га) -127 114 -27 98 -71 162
В = {-1, 2, 3, 7}, 6 = 2049 • 10727, с = 2 • З2 • 7, НОД (b + с, га) = 199.
ж)
і
0
1 2 3
4 5
а і
100
1 1 1
1 2
bi
100
101 201 302
503 1308
6? (mod
га)
-123
78 -91 97
-66 77
в = {-
-1,2,
3,7, 11, 13}, Ь = 101 • 201 •
503 • 1308,
с =
2 ¦ 3
•7-11 -
13, НОД (6 + с, га)
= 191.
з)
(
/
г
0
1
2
3 4 5
6 7
8
а і
111
1
1
2 1 4
1 6
2
bi
111
112
223
558 781 3682
4463 5562
3138
(mod га)
-128
95
-67
139 -40 163
-31 79
-115
9 1
8700 80
В = {-1,2, 5}, і = 111 • 781 • 8700, с = 27 • 5, НОД (b + с, п) = 59.
і 012345678
а, 96 1 2 2 5 1 1 1 1
bi 96 97 290 677 3675 4352 8027 3026 1700
i? (mod га) -137 56 -77 32 -107 79 -88 89 -77
В = {-1,2, 7,11}, Ь = 290 • 1700,с= 7-11, НОД (6 + c,n) = 47.
ОТВЕТЫ К УПРАЖНЕНИЯМ 249
к)
г 0123456789
а, 159 1 2 1 1 2 4 1 5 1
6,- 159 160 479 639 1118 2875 12618 15493 13550 3532
6? (mod га) -230 89 -158 145 -115 61 -227 50 -167 145
В = {-1,2, 5, 23, 29}, ь = 639 • 3532, с = 5 ¦ 29, НОД (6 4- с, га) = 97.
л)
г
0
1
2
3
4
5
6 7 8
а і
133
1
2
4
2
3
1 2 1
bi
133
134
401
1738
3877
13369
17246 12115 11488
b2 (mod га)
-184
83
-56
107
-64
161
-77 149 -88
= {-1,2, 7,11, 23}, 6 =
401 •
3877 •
17246 ¦
11488,
с = 2е ¦
7- 11, НОД (ь + с,п) =
§V.5
2. Наиболее трудоемкий — шаг 6). Время работы ограничивается величиной о( VJ —log р log raj = 0(А log га log Plog log P).
простые p^P ^
(Вопрос касался только шагов 1)-7); другим трудоемким этапом для очень больших га является нахождение линейно зависимых строк по модулю 2 в матрице показателей, соответствующих В-числам среди чисел <2 — п.)
3. а)
2 13 17 19 29 37 41 47 1030 14297 - - 1 - 2 - - -
