Лектор: Екатерина Малыгина
Лекции: Суббота 11:50 в 209 ауд.
Практика: Суббота 13:50 в 209 ауд.
Лекции: Пятница 13:50 в 217 ауд.
Практика: Пятница 15:30 в 217 ауд.
Экзамен: TBA TBA
| № | Тема | Дополнительные материалы | Практика |
|---|---|---|---|
| 1 | Теория сложности вычислений. |
--- | |
| 2 | Быстрые вычисления: Быстрое возведение в квадрат; Быстрое возведение в степень; Алгоритм Баррета; Приведение по модулю; Вычисление НОД'а; Извлечение квадратного корня. | п.1.1-1.4;п.1.6-1.7. (стр. 7--24) | Дэдлайн: 22.10 |
| 3 | Быстрые вычисления: Метод Карацубы-Офмана; Метод Шенхаге. | Конспект | Дэдлайн: 29.10 |
| 4 | Быстрые вычисления: Быстрое преобразование Фурье; Умножение с помощью БПФ. | Дэдлайн: 26.11 | |
| 5 | Быстрые вычисления: Метод Монтгомери: редукция и умножение. | Дэдлайн: 03.12 | |
| 6 | Вычисления символов Лежандра и Якоби. | п.9 (стр.31--38) | --- |
| 7 | Тесты на простоту: тест Ферма, тест Соловея-Штрассена, тест Миллера-Рабина. | Дэдлайн: 28.01 | |
| 8 | Построение и тестирование на простоту чисел Ферма и Мерсенна. | -- | Дэдлайн: 11.02 Программные реализации + Доказательство теоретических утверждений согласно конспекту. |
| 9 | Построение надежных простых, сильных простых и доказуемо простых чисел. | Дэдлайн: 25.02 Программные реализации генерации всех трех типов чисел. | |
| 10 | Задача факторизации: Метод пробных делений; Ро-метод Полларда; (p-1)-метод Полларда. | Дэдлайн: 04.03 Программные реализации всех трёх методов + оценки сложности. | |
11 |
Задача факторизации: Метод Диксона. Метод квадратичного решета. | Дэдлайн: 18.03 Программные реализации | |
12 |
Задача RSA: шифрование/расшифрование и подпись. | Дэдлайн: 01.04 Программные реализации | |
13 |
Дискретное логарифмирование: Метод Гельфонда; Ро-метод Полларда; Алгоритм Адлемана; Метод Полига-Хеллмана. | п.п.4.1-4.4. | Дэдлайн: 13.05 |
.jpg){kind=link}
.jpg){kind=link}