Содержание книги "Дискретная математика
:
модулярная алгебра, криптография, кодирование"
Предисловие
Введение
1. Множество
2. Функция
3. Отношение
4. Отношение эквивалентности
5. Каноническое разложение функции
6. Мощность множества. Счетные и несчетные множества
7. Мощность континуума
8. Кардинальные числа. Сравнение мощностей
Часть I. МОДУЛЯРНАЯ АЛГЕБРА
Глава 1. Делимость
1.1. Позиционная система счисления
1.2. Простые числа
1.3. Факторизация целых чисел
1.4. Наибольший общий делитель
1.5. Наименьшее общее кратное
1.6. Непрерывные (цепные) и подходящие дроби
Глава 2. Функции Мебиуса и Эйлера
2.1. Функции |_x_|, |x|, {x} для вещественного x
2.2. Мультипликативные функции
2.3. Функция и формула обращения Мебиуса
2.4. Функция Эйлера
Глава 3. Сравнения
3.1. Сравнение целых чисел
3.2. Свойства сравнений
3.3. Полная система вычетов
3.4. Приведенная система вычетов
3.5. Теоремы Эйлера и Ферма
3.6. Классы целых чисел по модулю m, взаимно простых с модулем m
3.7. Модулярные арифметические операции
Глава 4. Сравнения с одной переменной
4.1. Решение сравнения с переменными
4.2. Сравнения первой степени
4.3. Система сравнений первой степени
4.4. Сравнения любой степени с простым модулем
4.5. Сравнения произвольной степени по составному модулю
Глава 5. Сравнения второй степени
5.1. Квадратичные вычеты по простому модулю
5.2. Символ Лежандра
5.3. Символ Якоби
5.4. Квадратичные вычеты по составному модулю
Глава 6. Примитивные корни и индексы
6.1. Экспонента, примитивные корни, индексы
6.2. Примитивные корни по модулям pα и 2pα
6.3. Вычисление примитивных корней по модулям pα и 2pα
6.4. Индексы по модулям pα и 2pα
6.5. Индексы и вычеты
6.6. Индексы по модулю 2α
6.7. Индексы по любому составному модулю
Глава 7. Универсальные алгебры
7.1. Алгебры, подалгебры, гомоморфизм алгебр
7.2. Конгруэнции
Глава 8. Абстрактная алгебра
8.1. Полугруппы
8.2. Циклические полугруппы
8.3. Группы
8.4. Нормальные подгруппы, фактор-группы, теорема о гомоморфизме групп
8.5. Кольцо
8.6. Поле
8.7. Полиномиальные кольца
8.8. Идеал кольца
8.9. Линейное векторное пространство
8.10. Булева алгебра
8.11. Решетка
Глава 9. Конечные поля
9.1. Представленние конечного поля множеством классов вычетов по модулю неприводимого полинома
9.2. Поле разложения полинома xp-x
9.3. Цикличность мультипликативной группы поля
9.4. Задание поля корнем неприводимого полинома
9.5. Строение конечных полей
9.6. Изоморфизм полей Галуа
9.7. Автоморфизмы поля Галуа
9.8. Основные алгоритмы для конечных полей
Часть II. КРИПТОГРАФИЯ
Глава 10. Модулярная алгебра в криптографии
10.1. Криптография и ее цели
10.2. Проблема факторизации целых чисел
10.3. Проблема RSA
10.4. Проблема квадратичного вычета
10.5. Проблема дискретного логарифма
10.6. Проблема подмножества суммы
10.7. Проблема факторизации полиномов над конечным полем
10.8. Криптосистема RSA
10.9. Криптосистема Эль-Гамаля
10.10. Электронная цифровая подпись DSA
10.11. Криптографическая система Рабина
10.12. Рюкзачная схема шифрования Меркле–Хеллмана
10.13. Рюкзачная схема шифрования Хора–Ривеста
10.14. Вероятностные схемы шифрования с открытым ключом
10.15. Электронная цифровая подпись Фейге–Фиат–Шамира
10.16. Электронная цифровая подпись GQ
10.17. Электронная цифровая подпись Шнорра с хэш-функцией
10.18. Электронная цифровая подпись Ниберга–Рюппеля с извлечением сообщения
Глава 11. Криптография на эллиптических кривых над конечными полями
11.1. Эллиптические кривые
11.2. Эллиптические кривые над полем вещественных чисел
11.3. Эллиптические кривые в конечных полях
11.4. Сложение точек эллиптический кривой E(F) y2= x3+ax+b над полем F характеристики char(F) > 3
11.5. Сложение точек эллиптической кривой E(F) y2 = x3+ax2+bx+c над полем F характеристики char(F) = 3
11.6. Сложение точек суперсингулярной эллиптической кривой E(F) y2+cy = x3+ax+b над полем F характеристики char(F) = 2
11.7. Сложение точек несуперсингулярной эллиптической кривой E(F) y2+xy = x3+ax2+b над полем F характеристики char(F) = 2
11.8. Вычисление k*P
11.9. Порядок группы точек эллиптической кривой
11.10. Криптосистемы на эллиптических кривых над числовым конечным полем
Глава 12. Шифросистема NTRU на конечных полиномиальных кольцах
12.1. Проблема кратчайшего вектора в целочисленной решетке
12.2. Шифросистема NTRU
Глава 13. Блоковые и потоковые шифры
13.1. Блоковый шифр RC5-S
13.2. Потоковые шифры
Часть III. КОДИРОВАНИЕ
Глава 14. Линейные коды
14.1. Линейные пространства над полями Галуа
14.2. Расстояние Хэмминга
14.3. Порождающая и проверочная матрицы
14.4. Декодирование в ближайшее кодовое слово
14.5. Расстояние и корректирующая способность кода
14.6. Каноническая форма базисных матриц систематического кода
14.7. Декодирование линейного кода (декодер)
14.8. Бинарный код Хэмминга
Глава 15. Циклические коды
15.1. Порождающая и проверочная матрицы циклического кода
15.2. Канонические порождающая и проверочная матрицы циклического кода
15.3. Систематический кодер циклического кода
Глава 16. Коды Боуза–Чоудхури–Хоквингема (коды БЧХ)
16.1. Построение кодов БЧХ
16.2. Декодер Питерсона–Горенстейна–Цирлера
16.3. Алгоритм Питерсона–Горенстейна–Цирлера БЧХ-кода с исправлением t и менее ошибок
Глава 17. Коды сжатия информации
17.1. Алфавитное кодирование
17.2. Кодирование с минимальной избыточностью
17.3. Алгоритм Фано построения разделимой префиксной схемы алфавитного кодирования, близкого к оптимальному
17.4. Оптимальное кодирование
17.5. Алгоритм Хаффмана оптимальной разделимой префиксной схемы алфавитного кодирования
17.6. Кодер и декодер Прюфера для деревьев
Глава 18. Основы теории информации
18.1. Количество информации и энтропия
18.2. Свойства энтропии
18.3. Энтропия при непрерывном сообщении
18.4. Условная энтропия
18.5. Взаимная энтропия
Приложения
1. Множества, функции, отношения
2. Модулярная алгебра
3. Криптография
4. Кодирование
5. Информация и энтропия
Литература
Обозначения
