Теория чисел

Общая характеристика дисциплины

В результате изучения дисциплины "Теория чисел" студенты должны

знать:

» отношение делимости, деление с остатком;

» НОД и НОК целых чисел, алгоритм Евклида, свойства взаимно простых чисел;

» простые и составные числа, каноническое разложение, основная теорема арифметики;

» основные теоретико-числовые функции, их свойства и способы вычисления; оценки Чебышёва;

» асимптотический закон распределения простых чисел;

» определение числовых сравнений и их свойства; сравнения с неизвестным и методы их решения;

» алгоритм решения сравнений 1-й степени; алгоритм решения линейных диофантовых уравнений с двумя неизвестными;

» классы вычетов по модулю, группа обратимых (взаимно простых с модулем) классов вычетов;

» порядок обратимого класса вычетов;

» первообразные корни по модулю, теоремао существовании первообразного корня по простому модулю;

» система шифрования RSA;

» бинарный алгоритм возведения в степень по модулю, понятие псевдопростого числа, строго псевдопростого числа, способ генерации больших простых чисел;

уметь:

» решать задачи элементарной теории чисел (в частности, задачи на делимость и простейшие типы диофантовых уравнений);

» применять технику сравнений по модулю (или метод остатков), методы алгебры многочленов и математического анализа при решении указанных задач.

владеть:

» навыками в употреблении модулярной арифметики;

» стандартными эффективными вычислительными алгоритмами в элементарной теории чисел (на базе алгоритма Евклида и алгоритма быстрого возведения в степень по модулю).