О курсе
"Is mathematics useful, directly useful, as other sciences such as chemistry and physiology are? This is not an altogether easy or uncontroversial question, and I shall ultimately say No."
G.H. Hardy
Но по какой-то причине многие практические конструкции для сетевых коммуникаций и хранения данных происходят из абстрактных алгебраических объектов, а для анализа их работы требуются методы далекие от приложений.
Теория кодирования обеспечивает надежную передачу дискретных данных по физическим носителям. Казалось бы, при чем здесь упаковки шаров? В каком месте в работе оперативной памяти используется геометрия векторных пространств на конечными полями? С высокоскоростным интернетом легко не обращать на это никакого внимания, многое прочно прошито в "железо". Приложения криптографии же более функциональны: аутентификация сообщений, финансовые протоколы, децентрализованные инфраструктуры, скрытые вычисления и прочее, а в своей основе также используют арсенал алгебры, в том числе арифметики алгебраических многобразий.
Со всей потребностью в надежных схемах шифрования первый большой шаг был произведен только в 1970х годах, а все предшествующие решения можно рассмотреть как изощренные версии шифрования Цезаря. В действительности это закономерно, ведь не так-то просто собрать из шестеренок машину вычисляющую умножение в кольце вычетов и тем более сложение на эллиптической кривой над конечным полем. Удивительно однако, что нужные структуры открывшие новый горизонт были осмысленны в современной форме сильно раньше, а в нужной нам части, как и сами криптографические схемы, доступны пониманию самой широкой аудитории.
Для кого этот курс
С одной стороны студенты имеющие базовые математические сведения и желающие познакомиться с их применением на практике, а с другой желающие выучить сопутствующую математику.
Начальные требования
Приблизительно для половины задач достаточно знать и уметь применять алгоритм Евклида. Практически все нужные понятия будут рассмотрены на примерах, но для их усвоения желательно проверить себя на предлагаемых задачах. В случае затруднений с определениями следует обратиться к любому обстоятельному тексту (англоязычная вики, N. Koblitz A Course in Number Theory and Cryptography, Винберг Курс алгебры, ...). В вычислительных вопросах с длинной арифметикой будет полезно использовать Python; вычислительные среды типы Mathematica, SAGE могут пригодиться, но не обязательны. Вопросы помеченные как упражнения + задачи из pdf на самом деле основные, но так как проверять автоматически их решения невозможно они остаются на вашей совести. Особенного ранжирования по сложности нет, если что-то не получается, лучше отвлечься и вернуться к проблеме позже. Последняя часть самая практическая и ориентированна на взлом шифра, поэтому придется программировать.
Ниже ссылка на pdf с упражнениями и данные для последнего задания
https://drive.google.com/drive/folders/11Y-WtJsy14-J3kw4FxDelYfr8QEzPIsM?usp=sharing