==Конструктивная алгебра: алгоритмические основы обработки информации== ~~TOC~~ Курс поддерживается группой ((http://www.digdes.ru/ {{ :dd1.jpg }})) **Комментарии для потенциальных слушателей** Мое личное мнение: курс с таким названием и соответствующим ему содержанием должен быть естественным окончанием[[финальным аккордом]] программы обучения по Computer Science. Собственно, объяснение __теоретических основ__ алгоритмов обработки информации. Не всем этот уровень знаний нужен --- большинство программистов преспокойно обходятся самими алгоритмами ("дайте нам спецификации, а уж мы вам их запрограммируем!"). $ \mathfrak{Jedem} $ $ \mathfrak{das} $ $ \mathfrak{ Seine} $: выбирайте по себе --- "шпагу для дуэли, меч для битвы". Материала много и он в некоторых местах сложный, даже очень сложный. Много математики --- главным образом, алгебры; но и ((:probability теорию вероятностей)) тоже приходится подтаскивать. Я стараюсь подстраиваться под уровень слушателей, но иногда могу лишь слегка облегчить перенапряжение их мозгов. Уже выложенные материалы дадут представление чего ожидать. Но много чего еще не выложено, или выложено в полупереработанном мною (черновом) варианте. Приходится доделывать "на ходу". Не обессудьте! Июнь 2012. ---- ===Введение== ((:shannon Теория информации.)) Энтропия, информация, избыточность. Сжатие данных, ((:codes префиксные коды: Хаффмана)) и ((:shannon#код_шеннона_-_фано Шеннона-Фано)). ((:codes:lzw Код LZW)). Теоремы Шеннона. Коды, исправляющие ошибки. Шифрование. ===Алгебраические основы== ((:numtheory Начала теории целых чисел.)) Наибольший общий делитель ($ \operatorname{HOD} $). Алгоритм Евклида, теорема Ламе. Линейное представление $ \operatorname{HOD} $, континуанта. Делимость целых чисел, взаимно-простые числа, простые числа. Факторизация, метод Ферма. Функция Эйлера. ((:modular Модулярная арифметика.)) Сравнения. Вычисление $ A^B \pmod{M} $ --- алгоритм квадрирования-умножения. Теоремы Ферма и Эйлера. Решение линейных сравнений. Китайская теорема об остатках. ((:modular:index Индекс (дискретный логарифм) )). Первообразный (примитивный) корень по модулю. Решение сравнений вида $ x^n \equiv B \pmod{M} $. ((:complex_num Комплексные числа.)) Корни из единицы, первообразные корни из единицы. ((:polynomial Полином одной переменной.)) Схема Хорнера. Умножение полиномов --- классические и быстрые алгоритмы. Приводимость и неприводимость полиномов над $ \mathbb Q_{} $. ((:complex_num:circlediv Уравнения деления круга.)) ((:interpolation Интерполяция.)) ((:algebra2:vander Матрица Вандермонда)). Интерполяционный полином в форме Лагранжа. Тригонометрическая интерполяция. ((:interpolation:systemerr Интерполяция при наличии систематических ошибок в таблице.)) ((:dets:resultant Результант.)) Представление в детерминантной форме по методу Сильвестра и по методу Безу. Связь с $ \operatorname{HOD} $ полиномов, тождество Безу. Преобразование Чирнгауза. ===Криптография== ((:crypto История криптографии.)) Шифры Цезаря, Кардано, Виженера и скиталы. ((:crypto Криптография открытых ключей.)) Односторонняя функция (с секретом). Алгоритмы RSA и ((:cipher:elgamal ЭльГамаля)) построения ключей. Алгоритмы проверки числа на простоту. ((:crypto:pprime#вероятностно_простые_числа Вероятностно простые числа.)) Алгоритм ((:crypto:pprime#алгоритм_рабина-миллера Рабина-Миллера)). ((:crypto:attacks Криптоанализ.)) Факторизация --- алгоритмы Полларда. Атака малых показателей. ((:crypto:signature Аутентификация.)) Функции хэширования. Атака парадокса дней рождения. Цифровая подпись. ===Протоколы голосования, разделения секрета и консенсуса== ((:interpolation:shamir Схема Шамира разделения секрета.)) Децентрализованный протокол голосования. ===Поля Галуа== ((:gruppe:galois Основы теории конечных полей.)) Бесконечные поля. Конечные поля, представление элемента в векторном, полиномиальном и матричном видах. Умножение и обращение. Обобщенная теорема Ферма. Порядок элемента, примитивный элемент поля. Проблема обращения элемента в поле Галуа. Полиномы над $ \mathbf{GF}(2) $. Разложение $ x^{2^{n}} - x $. Неприводимые и примитивные полиномы. Полиномы над $ \mathbf{GF}(2^n) $. ===Кодирование== ((:codes:hamming Коды, исправляющие ошибки.)) Расстояние Хэмминга. Коды Адамара. Линейный код, порождающая и проверочная матрицы. Коды Хэмминга. ((:codes:cyclic Циклические коды.)) Систематическое и несистематическое кодирование. Свёртка. ((:codes:cyclic:bch Коды Боуза-Чоудхури-Хоквингема.)) Коды Рида-Соломона. ((:codes:raid Математика RAID-6.)) ===Быстрое преобразование Фурье== ((:interpolation:dft Дискретное преобразование Фурье.)) Интерполяция алгебраическая и тригонометрическая. ((:interpolation:dft#быстрое_преобразование_фурье Быстрое преобразование Фурье.)) ((:interpolation:dft:polynom_mult#числовое_преобразование_ферма Числовое преобразование Ферма.)) Алгоритм Шенхаге-Штрассена. Применения быстрого преобразования Фурье и числового преобразования Ферма. Умножение полиномов и целых чисел. Циклическая свертка. ==Ключевые алгоритмы== 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. Код Хемминга. ==Задачи== ☞ ((:codes:problems ЗДЕСЬ)) ==Вопросы к экзамену== ☞ ((:codes:questions ЗДЕСЬ)) ==Литература== **Берлекэмп Э.** //Алгебраическая теория кодирования//. М.Мир. 1971 **Блейхут Р.** //Быстрые алгоритмы цифровой обработки сигналов//. М. Мир. 1989 **Лидл Р., Нидеррайтер Г.** //Конечные поля. Том 1, том 2.// М.Мир. 1988. **Питерсон У., Уэлдон Э.** //Коды, исправляющие ошибки.// М.Мир. 1976. **Сэломон Д.** //Сжатие данных, изображений и звука.// М.Техносфера. 2006((:algorithms:test .)) **Утешев А.Ю., Черкасов Т.М., Шапошников А.А.** //Цифры и шифры.//СПб. СПбГУ. 2001. **Menezes A. J., van Oorschot P.C., Vanstone S.A.** //Handbook of Applied Cryptography.// (5th ed.) 2001. CRC Press ((:algorithms:bft .)) ((:users/au/share/bc122022 bc))