Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Стерлинга формула для п\ 11,
166,173 структура криптосистемы 63 суперсингулярная эллиптическая
кривая 204 Теорема о простых числах 12-13, 102 тест на простоту
- Адлемана-Померанца-Румели 151
- Адлемана-Хуана 215-216
- Коэна-Ленстры 151
- методом проб делением 140
- Миллера-Рабина 146
- на эллиптических кривых 213-215
- Пепина 216
- Поклингтона 212, 216
- Соловея-Штрассена 144
- Эткина 212,215 тор 194 триграмма 61 Факторизации метод
- квадратичного решета 180-182
- Монте-Карло 155-157
- Лолларда (р - 1) 217-219
- проб делением 140, 155 -ро-метод 155-159 -Ферма 106, 160-161
- цепных дробей 177-179 факторизация
-, разложение на множители 30-32,101
- с помощью эллиптических кривых
217, 221-226 факторная база 162 факторных баз алгоритм 115, 166 Ферма
- малая теорема 22, 140
- простое число 32, 58-59, 121, 216
- факторизация 106, 160-161 Фибоначчи числа 18, 86-87, 180, 237,
247
фиксированная биграмма 89 фиксированный элемент сообщения 71,72
Фробениус 207, 252 функция
- Вейерштрасса 193-194
- однонаправленная 94
- с замком (лазейкой) 93 Характеристика поля 36 Хассе теорема 197 хеш-функция 98 Цезарь Юлий 63 цепная дробь 174 циклическая группа 38 Частотный анализ 64
число Кармайкла 142-143, 152-153
число разрядов 3
Шестнадцатиричная система 12
шифрование 61
-, ключ 64, 91
-, матрица 80
-, преобразование 61
шифртекст 61
Шуфа алгоритм 202, 207
Эллиптическая кривая 188-189
- над конечным полем 196 эллиптическая функция 194-195 эллиптической кривой
- подгруппа кручения 195, 209 -редукция 209,219-221 Эль-Гамаля
- криптосистема 111, 121, 206-207
- система подписи 121
Эткина тест на простоту 212, 215 Якоби символ 54
ПРЕДИСЛОВИЕ
«. .. Гаусс, а также другие математики, по-видимому, справедливо утверждали, что существует, по крайней мере, одна наука (теория чисел), которая, ввиду своей отдаленности от обыденной человеческой деятельности, остается чистой и благородной.»
— G.H.Hardy, A Mathematician's Apology, 1940
Харди был бы удивлен и, возможно, огорчен ростом интереса к приложениям теории чисел в таких областях «обычной человеческой деятельности», как передача информации (коды, исправляющие ошибки) и криптография (секретные коды). Не прошло и полувека с того момента, как Харди написал приведенные выше строки, а уже не кажется невероятным (хотя пока этого не произошло), что АНБ (Аген-ство Национальной Безопасности, работа которого в области криптографии обеспечивает потребности правительства США) будет требовать предварительной экспертизы для разрешения на публикацию теоретических работ по определенным направлениям теории чисел.
Одной из причин, благодаря которым отдельные вопросы, интересовавшие специалистов по теории чисел, превратились в новое направление, названное «вычислительной теорией чисел», явился быстрый рост мощности и сложности компьютеров.
Книга почти не предполагает знания основ алгебры или теории чисел. Ее цель — ввести читателя в те области арифметики, как классические, так и самые современные, которые находятся в центре внимания приложений, особенно криптографии. По этой причине мы избрали алгоритмический подход, выделяя особенно вопрос оценки эффективности методов, предлагаемых теорией. Особенностью нашей книги является изложение совсем недавно разработанных приложений теории эллиптических кривых (глава VI). Эллиптические кривые долгое время были центральной темой некоторых направлений математики. Теперь оказалось, что арифметика эллиптических кривых может иметь и практические приложения.
Во все главы включены задачи, которые должны помочь читателям, интересующимся более широким кругом вопросов, полнее усвоить изучаемый материал.
vi ПРЕДИСЛОВИЕ
Первые две главы посвящены общим вопросам. Студентам, не имевшим дела с алгеброй (расширениями полей, конечными полями) или элементарной теорией чисел (сравнениями), изложение покажется весьма сжатым, но они могут обратиться к более подробным курсам. С другой стороны, читатели с большей математической подготовкой, возможно, лишь бегло просмотрят эти главы, остановившись только на некоторых упражнениях.
При соответствующей подготовке слушателей первые пять глав можно взять за основу семестрового курса. Главы III—VI можно использовать в семестровом курсе, продолжающем семестровый курс элементарной теории чисел.
Зависимость между материалом глав следующая (исходя из ссылок в главах V и VI на предыдущий материал):
Глава I
Глава II
/ I
Глава III Глава V
Глава IV
За основу этой книги взяты курсы, прочитанные в университете штата Вашингтон (Сиэтл) в 1985-86 годах и в Институте математики (Мадрас, Индия) в 1987 году. Мне приятно поблагодарить Гэри Нельсон и Дугласа Линда за апробацию рукописи и полезные замечания.
Рисунок на фронтисписе, принадлежащий профессору А. Т. Фоменко из Московского государственного университета, иллюстрирует тему книги. Обратите внимание, что коды десятичных цифр на стенах здания вовсе не случайны.
