Описание:Курс посвящен теоретико-числовым алгоритмам и их применениям в криптографии. Обсуждаются детерминированные и вероятностные алгоритмы, оценки их сложности. Среди рассматриваемых алгоритмов - алгоритм Евклида, вычисление символов Лежандра и Якоби, быстрый алгоритм возведения в степень, алгоритмы решения квадратичных сравнений, методы отсеивания составных чисел, быстрые алгоритмы умножения целых чисел, разложение многочленов на множители над конечными полями, алгоритмы, распознающие простоту чисел, алгоритмы факторизации и дискретного логарифмирования, LLL-алгоритм и его применения. Обсуждаются также алгоритм Диффи-Хеллмана обмена ключами, алгоритм RSA и условия его безопасного использования, алгоритмы электронной цифровой подписи.