Теория чисел
Общая характеристика дисциплины
В результате изучения дисциплины "Теория чисел" студенты должны
знать:
» отношение делимости, деление с остатком;
» НОД и НОК целых чисел, алгоритм Евклида, свойства взаимно простых чисел;
» простые и составные числа, каноническое разложение, основная теорема арифметики;
» основные теоретико-числовые функции, их свойства и способы вычисления; оценки Чебышёва;
» асимптотический закон распределения простых чисел;
» определение числовых сравнений и их свойства; сравнения с неизвестным и методы их решения;
» алгоритм решения сравнений 1-й степени; алгоритм решения линейных диофантовых уравнений с двумя неизвестными;
» классы вычетов по модулю, группа обратимых (взаимно простых с модулем) классов вычетов;
» порядок обратимого класса вычетов;
» первообразные корни по модулю, теоремао существовании первообразного корня по простому модулю;
» система шифрования RSA;
» бинарный алгоритм возведения в степень по модулю, понятие псевдопростого числа, строго псевдопростого числа, способ генерации больших простых чисел;
уметь:
» решать задачи элементарной теории чисел (в частности, задачи на делимость и простейшие типы диофантовых уравнений);
» применять технику сравнений по модулю (или метод остатков), методы алгебры многочленов и математического анализа при решении указанных задач.
владеть:
» навыками в употреблении модулярной арифметики;
» стандартными эффективными вычислительными алгоритмами в элементарной теории чисел (на базе алгоритма Евклида и алгоритма быстрого возведения в степень по модулю).