Основы криптографии

Понятие информации и её кодирование. Помехоустойчивость, увеличение скорости передачи информации, защита информации.
Секретные и открытые ключи. Алфавитное кодирование. Префиксные коды. Неравенство Крафта—МакМиллана. Теорема о минимальной длине префиксного кода.
Циклические коды. Конечные поля. Неприводимые многочлены.
Криптографические протоколы. Протокол для игры ``Орёл-решка’’ по телефону. Электронная подпись.
Сложность арифметических операций. Алгоритм Евклида. Операции в кольце вычетов. Дискретное преобразование Фурье. Наименьший первообразный корень.
Проверка числа на простоту: решето Эратосфена, критерий Вильсона, малая теорема Ферма, числа Кармайкла, тесты Соловея—Штрассена, Рабина—Миллера.
Полиномиальный тест проверки на простоту.
Построение больших простых чисел. Критерий Люка. Числа Мерсенна.
Алгоритмы разложения натуральных чисел на множители. Метод квадратичного решета.
1Криптографическая система RSA. Задача об укладке рюкзака. ``Рюкзачная’’ система шифрования. Криптографические хеш-функции.
Китайская теорема об остатках. Арифметический вариант шифра Виженера.