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

Весенний семестр 2024-25

1. Компьютерные сети. Обзор, классификация. Понятие протокола. Уровневая модель описания сетевых протоколов. Примеры протоколов физического уровня (CSMA/CD, Ethernet, Token Ring, DQDB). Стек интернетовских протоколов TCP/IP. Программирование с использованием интерфейса BSDI-сокетов.
• Простейший пример пары client--server, использующий интерфейс сокетов, реализованный на C++.
• Универсальный (асинхронный) Internet-клиент: asyncli.cpp
• Пример пары клиент--сервер, реализованный на Яве и на C++.
• Пример на использование протокола UDP: синхронное рисование в двух окнах (проект "SDraw.zip").
• Проект "Файловый сервер":
  • описание;
  • исходные тексты.
• Сетевое программирование: список задач.
2. Параллельное программирование: нити (потоки, легковесные процессы) и их синхронизация.

Элементы теории чисел

Содержание лекции:

• Кольцо вычетов по модулю m
• Малая теорема Ферма, китайская теорема об остатках, теорема Эйлера
• Основные алгоритмы теории чисел: алгоритм Евклида, расширенный алгоритм Евклида, быстрое возведение в степень, алгоритм в китайской теореме об остатках, извлечение квадратного корня в поле вычетов по модулю p.
• Тест простоты Ферма и кармайкловы числа
• Вероятностный тест простоты Миллера-Рабина
• Кодирование с открытым ключом, схема RSA
• Алгоритмы факторизации (разложения числа на множители): ρ-алгоритм Полларда и p-1 алгоритм Полларда.

Презентация: теория чисел в криптографии

Файл numberth.py:
реализация базовых алгоритмов теории чисел на Python

• Вычисление наибольшего общего делителя двух целых чисел
• Расширенный алгоритм Евклида — представление наибольшего общего делителя d целых чисел m, n в виде линейной комбинации этих чисел с целыми коэффициентами:

  d = u·m + v·n

• Вычисление обратного элемента в кольце вычетов по модулю m
• Алгоритм быстрого воззведения в степень в кольце вычетов по модулю m

• Необязательная задача (ее можно выбрать вместо любой из перечисленных выше задач): факторизовать целое число с помощью алгоритма Ленстра на эллиптических кривых.