Название спецкурса: Информационные технологии
Ведет спецкурс Нестеренко Юрий Валентинович, доктор физико-математических наук, профессор по кафедре теории чисел, член-корреспондент РАН.
День недели: вторник, 16:40, 32 кабинет.
Программа спецкурса:
Специальный курс Информационные технологии подготовлен для инженерного класса СУНЦ МГУ, но лекции могут посещать все, кому интересна не только теоретическая математика, но и её далеко не всегда очевидные приложения. Он будет читаться в течение учебного года, один раз в неделю. Основное содержание курса составляют так называемые информационные технологии, возникшие сравнительно недавно, в связи с образовавшимися потребностями, и переживающие сейчас период становления, они широко обсуждаются, некоторые уже используются, а другие в ближайшее время получат широкое распространение. Инженерная деятельность в этой области направлена на создание информации и механизмов её обработки, безопасного хранения и передачи, а в роли инструментов выступают математические алгоритмы, основанные на методах теории чисел, алгебры, дискретной математики. Важную часть информационных технологий составляет криптография.Опишем подробнее содержание этого специального курса.
- Алгоритмы и сложность.
Алгоритм Евклида и теорема Ламе о сложности этого алгоритма.Решение уравнений и сравнений. Быстрый алгоритм возведения в степень. Быстрое умножение целых чисел. Вероятностные алгоритмы и их сложность. Вероятностные методы отсеивания составных чисел. Построение больших простых чисел. Доказательство простоты чисел. Первообразные корни и дискретное логарифмирование. Задача разложения целых чисел на множители. Конечные поля. Эллиптические кривые.
- Криптографические примитивы.
Псевдослучайные последовательности чисел.Алгоритм обмена ключами. Алгоритм шифрования RSA. Простейшие булевы функции.Хеш-функции. Алгоритм хеширования SHA-256.Основные алгоритмы шифрования с открытым ключом. Криптосистема Эль-Гамаля.Криптосистема Рабина.
- Информационные технологии.
Электронная подпись. Электронная подпись с помощью эллиптических кривых. Схемы обязательств. Подбрасывание монеты по телефону. Подтверждение выбора (доказательство с нулевым разглашением). Разделение секрета. Протокол аутентификации. Система электронного голосования. Технологии блокчейн. Криптовалюты.
Слушателям спецкурса будут предложены самостоятельные творческие работы.Программы можно будет писать на языке Питон.
- Построение больших простых чисел. Нужно построить алгоритм и соответствующую компьютерную программу, производящие простые числа на заданном интервале. Например, от до или от до .
- Электронное голосование. Построить систему удалённого электронного голосования для определения рейтинга преподавателей СУНЦ МГУ.
Вопрос в том, как организовать систему голосования, для того, чтобы все голоса были переданы по обычным каналам сети Интернет, а затем обработаны и сохранены в центральном компьютере с соблюдением некоторых требований. Например, в голосовании участвуют только допущенные к этому лица, никто (комиссия по проведению выборов, участники голосования, посторонние люди и др.) не может узнать, кто из участников голосования и как проголосовал, результаты голосования никому не известны до окончания голосования.
- Решение показательных сравнений. Разработать быстрый алгоритм для решения сравнений вида , где a, b— натуральные числа, взаимно простые с 10, а n — достаточно большое натуральное число. Подготовить соответствующую компьютерную программу, сосчитать несколько примеров, скажем при n>1000.