skip to Main Content

Название спецкурса: Информационные технологии

Ведет спецкурс Нестеренко Юрий Валентинович, доктор физико-математических наук, профессор по кафедре теории чисел, член-корреспондент РАН.

День недели: вторник, 16:40, 32 кабинет.

 

Программа спецкурса:

 

Специальный курс Информационные технологии подготовлен для инженерного класса СУНЦ МГУ, но лекции могут посещать все, кому интересна не только теоретическая математика, но и её далеко не всегда очевидные приложения. Он будет читаться в течение учебного года, один раз в неделю. Основное содержание курса составляют так называемые информационные технологии, возникшие сравнительно недавно, в связи с образовавшимися потребностями, и переживающие сейчас период становления, они широко обсуждаются, некоторые уже используются, а другие в ближайшее время получат широкое распространение. Инженерная деятельность в этой области направлена на создание информации и механизмов её обработки, безопасного хранения и передачи, а в роли инструментов выступают математические алгоритмы, основанные на методах теории чисел, алгебры, дискретной математики. Важную часть информационных технологий составляет криптография.Опишем подробнее содержание этого специального курса.

 

  1. Алгоритмы и сложность.

Алгоритм Евклида и теорема Ламе о сложности этого алгоритма.Решение уравнений и сравнений. Быстрый алгоритм возведения в степень. Быстрое умножение целых чисел. Вероятностные алгоритмы и их сложность. Вероятностные методы отсеивания составных чисел. Построение больших простых чисел. Доказательство простоты чисел. Первообразные корни и дискретное логарифмирование. Задача разложения целых чисел на множители. Конечные поля. Эллиптические кривые.

  1. Криптографические примитивы.

Псевдослучайные последовательности чисел.Алгоритм обмена ключами. Алгоритм шифрования RSA. Простейшие булевы функции.Хеш-функции. Алгоритм хеширования SHA-256.Основные алгоритмы шифрования с открытым ключом. Криптосистема Эль-Гамаля.Криптосистема Рабина.

  1. Информационные технологии.

Электронная подпись. Электронная подпись с помощью эллиптических кривых. Схемы обязательств. Подбрасывание монеты по телефону. Подтверждение выбора (доказательство с нулевым разглашением). Разделение секрета. Протокол аутентификации. Система электронного голосования. Технологии блокчейн. Криптовалюты.

 

Слушателям спецкурса будут предложены самостоятельные творческие работы.Программы можно будет писать на языке Питон.

 

  1. Построение больших простых чисел. Нужно построить алгоритм и соответствующую компьютерную программу, производящие простые числа на заданном интервале. Например, от до    или от   до   .
  2. Электронное голосование. Построить систему удалённого электронного голосования для определения рейтинга преподавателей СУНЦ МГУ.

Вопрос в том, как организовать систему голосования, для того, чтобы все голоса были переданы по обычным каналам сети Интернет, а затем обработаны и сохранены в центральном компьютере с соблюдением некоторых требований. Например, в голосовании участвуют только допущенные к этому лица, никто (комиссия по проведению выборов, участники голосования, посторонние люди и др.) не может узнать, кто из участников голосования и как проголосовал, результаты голосования никому не известны до окончания голосования.

  1. Решение показательных сравнений. Разработать быстрый алгоритм для решения сравнений вида , где a, b— натуральные числа, взаимно простые с 10, а n — достаточно большое натуральное число. Подготовить соответствующую компьютерную программу, сосчитать несколько примеров, скажем при n>1000.