Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
§VI.4
1. НОД (2к - 1, га) = га, но НОД (3* - 1, га) = 127, га = 127 • 421.
2. Вероятность того, что случайный вычет а Є (Z/pZ)* удовлетворяет условию р\(ак — 1), равна НОД (к,р — 1)/(р — 1). Так как имеется мало шансов, что ак — 1 будет делиться на какой-либо другой делитель га, то это же число служит оценкой вероятности того, что НОД (ак — 1, га) = р.
3. а) 3 из 41. б) 22 из 41. в) 25 из 127. г) 68 из 127. д) 105 из 399.
4. Выбрать к = 26 • З4 • 52. Далее указаны: первое значение а, для которого метод дает делитель, сам этот делитель, значение Ai1 на котором алгоритм заканчивается, a) 1,37,23. б) 2, 71, 2е ¦ З4 • 5. в) 1, 67, 26 • З4 • 5. г) 1,47,26 • 3. д) 2,79,26 • З4 • 52. е) 1,73,26-3. ж) 5,53,22. з) 4, 59, 26 • З2. и) 1,47,2е • 3. к) 3, 97,2е ¦ 3. л) 1, 61, 26 • З4 ¦ 52.
5. Если бы реализовалась последняя возможность, то это означало бы, что V(к\/I)P (mod р) = О (mod р) для некоторого /' < /, тогда как (ki/l)P (mod ф О (mod р). Однако /' — это произведение простых чисел /* < /, а наш выбор показателей в (2) гарантировал для каждого такого /*, что наивысшая степень V,
254
ОТВЕТЫ К УПРАЖНЕНИЯМ
которая могла бы делить порядок P (mod р) в E (mod р), заведомо содержится в (Z*)"'-, т.е. в ki/l.
6. а) Если п делится лишь на простые числа р, сравнимые с 3 по модулю 4, то для каждого р\п на кривой E (mod р) всегда имеется в точности р+1 точек (см. упражнение 7 а) к § 1 для случая а — —1; однако те же аргументы применимы при любом а). Если при этом р+1 для каждого р\п делится на большое простое число, то изменение а не даст результата, б) Если п делится лишь на простые числа р, сравнимые с 2 по модулю 3, то всегда имеется р + 1 точек (см. упражнение 76) к § 1); и опять, если р + 1 для каждого р\п делится на большое простое число, то изменение 6 не приведет к результату.
7. Порождать пары (Е, P)1 где E имеет уравнение у1 = х(х — а)(х — Ъ). Тогда E имеет четыре точки порядка 2 (включая точку в бесконечности) (см. упражнение 4 а) к §VI.l); для этого можно сначала случайным образом выбирать atx,yo и затем полагать у = х(х — а)уо и b = х — ууо-
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Абелева группа 37
-, тип 197
автоморфизм 35, 41
Адлемана-Померанца-Румели тест на простоту 151
Адлемана-Хуана тест на простоту 215-216
алгебраический элемент 35
алгоритм 10
- Берлекампа 116
- вероятностный 95, 104-105, 14Ы42
- детерминистический 142
- дискретного логарифмирования 113-118
- индексный 114-118
- Силвера-Полига-Хеллмана 113-114,208
- факторных баз 115-116, 166
- Шуфа 202, 207 алфавит 92
аутентичность, подлинность 97, 105
аффинная плоскость 192
аффинное отображение 64, 67, 76, 84
Бесконечно удаленная прямая 192
бесконечность 193
- - точка 189, 193 биграмма 61
бит 3
«больших и малых шагов» метод 114
Бонд Джеймс 90, 210, 236, 239 бросание монетки 100, 106, 240 быстрорастущий набор 123 Л-число 162, 180-181
Вейля
- гипотеза 198
- спаривание 204 векторное пространство 34 вероятностное шифрование 99 вероятностный алгоритм 95,
104-105, 141-142
вещественные точки на эллиптической кривой 199, 251
взаимно простые (числа) 16
Виженера шифр 74
256
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Вильсона теорема 28 возведение в степень 25-26, 107
- в кольце 26, 107 временные оценки 5
для
- алгоритма Евклида 15-16, 18, 19
- алгоритма факторных баз 166-172
- арифметических операций 3-8
- возведения в степень в кольце вычетов 26
- извлечения квадратного корня по модулю р 57-58
- метода квадратичного решета 185
- нахождения обратного 21
- перевода в новую систему счисления 10-11
- ро-метода 158-159
- теста Миллера-Рабина на простоту 153
- точек на эллиптической кривой 201
- факторизации на эллиптической кривой 224-226
- факторизационных алгоритмов 171-172
вскрытие кода 63 вычет
- квадратичный 49
- наименьший абсолютный 162
- по модулю т 20-21, 219
Галуа расширение поля 35 гауссова сумма 50, 52, 151 гауссовы числа 19, 42, 48, 193 гладкая точка 189 гладкое целое 113 глобальная эллиптическая кривая 208 граф 130
группа
- абелева 37
- циклическая 38
Двоичная
- операция 3
- система счисления 1-3 двоичный разряд (бит) 3 делимость 13
- точная 13 делитель 13
- нетривиальный 13
- собственный 13 делящая точка 195 детерминистический алгоритм
142
дешифрование 61 -, ключ 91 -, преобразование 61 дзета-функция 198
- на эллиптической кривой 198 дискретный логарифм 107-108
- на эллиптической кривой 203 DES (стандарт шифрования
данных) 111-112 DSS (стандарт цифровой подписи) 111-113
Евклида алгоритм 14-15
- для гауссовых чисел 19-20
- для многочленові^
Жермен Софи 233
- простое число 233
Закон сложения на эллиптической кривой 190 зашифрование 61
Изоморфизм 35
индексный алгоритм 114-118
Казанова 92-93 квадратичная взаимность 51, 54
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
257
квадратичное решето 180-182 квадратичный
- вычет 49
- невычет 49
- характер 196
