Основная профессиональная образовательная программа высшего образования

Содержание основных разделов (тем) курса

Тема 1. Введение.
Место теории чисел среди других математических дисциплин. Приложения теории чисел. Краткая история развития теории чисел Литература по дисциплине.
Тема 2. Элементы теории чисел.
Квадратичные вычеты. Символы Лежандра и Якоби. Закон квадратичной взаимности Гаусса. Квадратные корни: метод Цассенхауза-Кантора. Классы вычетов, вычисления в кольцах вычетов. Строение мультипликативной группы кольца Китайская теорема об остатках и ее использование при решении теоретико-числовых задач.
Тема 3. Цепные дроби.
Понятие конечной и бесконечной цепной дроби. Подходящие дроби и их свойства. Представление действительных чисел цепными дробями. Теорема Лагранжа о представлении квадратичных иррациональностей периодическими цепными дробями. Цепные дроби как наилучшие рациональные приближения действительных чисел.
Тема 4. Сложность арифметических операций.
Сложность операций с целыми числами. Сложность операций в кольце вычетов. Сложность алгоритма Евклида. Модульная арифметика и ее использование. Вычисления с многочленами. Дискретное преобразование Фурье. Теорема Чебышева о распределении простых чисел.
Тема 5. Алгоритмы проверки чисел на простоту.
Решето Эратосфена. Критерий Вильсона. Тест на основе малой теоремы Ферма. Псевдопростые числа и числа Кармайкла. Построение чисел Кармайкла и псевдопростых чтисел. Тест Соловея-Штрассена. Эйлеровы псевдопростые числа по данному основанию. Сильно псевдопростые числа. Тест Рабина-Миллера.
Тема 6. Алгоритмы построения больших простых чисел.
Критерий Люка. Теорема Сэлфриджа. Числа Ферма, критерий их простоты. Теорема Поклингтона. Теорема Диемитко. Метод Маурера. Метод Михалеску. Обзор методов. Числа Мерсенна. Тест Люка-Лемера.
Тема 7. Алгоритмы факторизации чисел.
Метод Полларда. Алгоритм Полларда-Штрассена. Факторизация Ферма. Алгоритм Диксона. Алгоритм Бриллхарта-Моррисона. Метод квадратичного решета. метод Полларда. Алгоритм Шенкса.