УказательРазделыОбозначенияАвторО проектеEnglish version


{}_{.} Курс поддерживается группой


Конструктивная алгебра: алгоритмические основы обработки информации


Комментарии для потенциальных слушателей

Мое личное мнение: курс с таким названием и соответствующим ему содержанием должен быть естественным окончанием1) программы обучения по Computer Science. Собственно, объяснение теоретических основ алгоритмов обработки информации. Не всем этот уровень знаний нужен — большинство программистов преспокойно обходятся самими алгоритмами («дайте нам спецификации, а уж мы вам их запрограммируем!»). \mathfrak{Jedem} \mathfrak{das} \mathfrak{ Seine}: выбирайте по себе — «шпагу для дуэли, меч для битвы».

Материала много и он в некоторых местах сложный, даже очень сложный. Много математики — главным образом, алгебры; но и теорию вероятностей тоже приходится подтаскивать. Я стараюсь подстраиваться под уровень слушателей, но иногда могу лишь слегка облегчить перенапряжение их мозгов.

Уже выложенные материалы дадут представление чего ожидать. Но много чего еще не выложено, или выложено в полупереработанном мною (черновом) варианте. Приходится доделывать «на ходу». Не обессудьте!

Июнь 2012.


Введение

Теория информации. Энтропия, информация, избыточность. Сжатие данных, префиксные коды: Хаффмана и Шеннона-Фано. Код LZW. Теоремы Шеннона. Коды, исправляющие ошибки. Шифрование.

Алгебраические основы

Начала теории целых чисел. Наибольший общий делитель (\operatorname{HOD}). Алгоритм Евклида, теорема Ламе. Линейное представление \operatorname{HOD}, континуанта. Делимость целых чисел, взаимно-простые числа, простые числа. Факторизация, метод Ферма. Функция Эйлера.

Модулярная арифметика. Сравнения. Вычисление A^B \pmod{M} — алгоритм квадрирования-умножения. Теоремы Ферма и Эйлера. Решение линейных сравнений. Китайская теорема об остатках.

Индекс (дискретный логарифм) . Первообразный (примитивный) корень по модулю. Решение сравнений вида x^n \equiv B \pmod{M}.

Комплексные числа. Корни из единицы, первообразные корни из единицы.

Полином одной переменной. Схема Хорнера. Умножение полиномов — классические и быстрые алгоритмы. Приводимость и неприводимость полиномов над \mathbb Q_{}. Уравнения деления круга. Интерполяция. Матрица Вандермонда. Интерполяционный полином в форме Лагранжа. Тригонометрическая интерполяция.

Результант. Представление в детерминантной форме по методу Сильвестра и по методу Безу. Связь с \operatorname{HOD} полиномов, тождество Безу. Преобразование Чирнгауза.

Криптография

История криптографии. Шифры Цезаря, Кардано, Виженера и скиталы.

Криптография открытых ключей. Односторонняя функция (с секретом). Алгоритмы RSA и ЭльГамаля построения ключей.

Алгоритмы проверки числа на простоту. Вероятностно-простые числа, псевдопростые числа, числа Кармайкла. Алгоритм Миллера-Рабина.

Криптоанализ. Факторизация — алгоритмы Полларда. Атака малых показателей.

Аутентификация. Функции хэширования. Атака парадокса дней рождения. Цифровая подпись.

Поля Галуа

Основы теории конечных полей. Бесконечные поля. Конечные поля, представление элемента в векторном, полиномиальном и матричном видах.

Умножение и обращение. Обобщенная теорема Ферма. Порядок элемента, примитивный элемент поля. Проблема обращения элемента в поле Галуа.

Полиномы над \mathbf{GF}(2). Разложение x^{2^{n}} - x. Неприводимые и примитивные полиномы. Полиномы над \mathbf{GF}(2^n).

Кодирование

Коды, исправляющие ошибки. Расстояние Хэмминга. Коды Адамара. Линейный код, порождающая и проверочная матрицы. Коды Хэмминга.

Циклические коды. Систематическое и несистематическое кодирование. Свёртка.

Коды Боуза-Чоудхури-Хоквингема. Коды Рида-Соломона. Математика RAID-6.

Быстрое преобразование Фурье

Дискретное преобразование Фурье. Интерполяция алгебраическая и тригонометрическая.

Быстрое преобразование Фурье.

Числовое преобразование Ферма. Алгоритм Шенхаге-Штрассена.

Применения быстрого преобразования Фурье и числового преобразования Ферма. Умножение полиномов и целых чисел. Циклическая свертка.

Ключевые алгоритмы

  1. Коды Хаффмана и Шеннона-Фано.
  2. \operatorname{HOD}(A,B) и линейное представление.
  3. \phi(A)
  4. A^B \pmod{M} (со всевозможными упрощающими соображениями)
  5. Ax\equiv B \pmod{M}
  6. A_1x\equiv B_1 \pmod{M_1},\dots,A_kx\equiv B_k \pmod{M_k}
  7. Индекс. x^n \equiv B \pmod{p}
  8. RSA схема выбора ключей; алгоритмы шифрования и цифровой подписи
  9. Вероятностный алгоритм проверки простоты числа.
  10. Код Хемминга.

Задачи

находятся ЗДЕСЬ

Вопросы к экзамену

находятся ЗДЕСЬ

Литература

Берлекэмп Э. Алгебраическая теория кодирования. М.Мир. 1971

Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М. Мир. 1989

Лидл Р., Нидеррайтер Г. Конечные поля. Том 1, том 2. М.Мир. 1988.

Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.Мир. 1976.

Сэломон Д. Сжатие данных, изображений и звука. М.Техносфера. 2006.

Утешев А.Ю., Черкасов Т.М., Шапошников А.А. Цифры и шифры.СПб. СПбГУ. 2001.

Menezes A. J., van Oorschot P.C., Vanstone S.A. Handbook of Applied Cryptography. (5th ed.) 2001. CRC Press

1) финальным аккордом

2018/01/21 13:57 редактировал au