Модель системы передачи информации
Схема Шеннона: источник, кодер, канал, декодер, приёмник. Количество информации, энтропия, избыточность.
Теория
Статьи расположены в рекомендуемом порядке изучения: от модели передачи информации и сжатия — к помехоустойчивым кодам, асимметричной криптографии и теории чисел, на которой она построена.
1. Основы теории информации
2. Эффективное кодирование (сжатие)
Код Хаффмана
Оптимальный префиксный код: дерево строится снизу вверх объединением двух самых редких узлов.
Код Шеннона–Фано
Префиксный код «сверху вниз»: символы делятся на группы с близкими суммарными частотами.
3. Помехоустойчивое кодирование
Код Хэмминга
Линейный код, исправляющий одну ошибку: биты чётности на позициях 2ᵏ и синдром — номер ошибочного бита.
Код Адамара
Код из строк матрицы Адамара: расстояние n/2, декодирование по максимуму корреляции.
4. Криптография
Классические шифры
Перестановка и замена, шифр Цезаря, частотный анализ. Принцип Керкгоффса.
Шифр Эль-Гамаля
Асимметричное шифрование на задаче дискретного логарифма: ключи, сеансовый ключ k, стойкость.
Простые числа и тесты простоты
Пробное деление, тест Ферма, Миллер–Рабин и доказательство простоты по критерию Поклингтона.
5. Алгебра и теория чисел
Моноиды
Множество с ассоциативной операцией и нейтральным элементом. Полугруппы, группы, примеры.
Диофантовы уравнения
Линейные уравнения в целых числах, расширенный алгоритм Евклида, соотношение Безу.
Сравнения по модулю
Арифметика остатков, быстрое возведение в степень, теоремы Эйлера и Ферма, китайская теорема.
Вычеты и первообразные корни
Кольцо ℤₘ, функция Эйлера, порядок элемента, первообразные корни, дискретный логарифм.