Эффективность алгоритмов. О- большое нотация.
Принцип разделяй и властвуй.
Сортировка делением пополам и разбиением по значениям.
Представление больших чисел и умножение по Карацуба.
Преобразование Фурье и быстрый метод умножения.
Умножение матриц методом Штрассена.
Групповая и бигрупповая алгебра и изоморфизм последних с алгеброй матриц.
Алгоритм Евклида и вычисление обратной по модулю другого числа.
Понятие равномерности и их влияние на эффективность работы алгоритмов.
Основы криптографии RSA.
Тесты на простоту Ферма, Эйлера и Рабина-Миллера.
Псевдопростые числа Фибоначчи и Люка.
Тест Фробениуса.
Круговые многочлены и кандидаты на простые числа.
Теорема Люка (о простоте и образующей), тест Пепина для чисел Ферма.
Доказательство простоты при наличии разложения n-1 до величины не меньше, чем .
n+1 тест простоты и тест Люка для чисел Мерсенна.
Тест AKS.
Факторизация чисел методом квадратов и методом Лемана.
Ро-метод Полларда.
Детские шаги, гигантские шаги.
Число классов и факторизация за О(exp(ln(n)(1+o(1)))).
Метод квадратичного решета QS.
Метод решета числового поля NFS.
Эллиптические кривые, рациональные точки на кривой.
Конечность ранга и структура периодической части.
Диофантовые уравнения (системы уравнений), приводящие к нахождению рациональных точек на кривой.
Задача о совершенном кирпиче.
Задача о латинском квадрате, состоящем из квадратов.
Задача о пяти квадратах со второй разницей, равным 2.
Алгоритмы поиска и установления структуры группы точек конечного порядка.
Алгоритмы вычисления ранга и базиса образующих.
Факторизация с использованием эллиптических кривых.
Доказательство простоты с использованием эллиптических кривых.