Программа курса теория чисел для экономического потока

ТЕОРИЯ ЧИСЕЛ ДЛЯ ЭКОНОМИЧЕСКОГО ПОТОКА

1. 
   Делимость целых чисел. Алгоритм Евклида и его сложность.
   
2. 
   Простые числа. Основная теорема арифметики.
   
3. 
   Оценки Чебышева для функции .
   
4. 
   Теорема Дирихле о приближении действительных чисел рациональными. Следствие из теоремы Дирихле для иррациональных чисел.
   
5. 
   Конечные непрерывные дроби. Представление рационального числа непрерывной дробью.
   

6. 
   Бесконечные цепные дроби. Представление действительного иррационального числа бесконечной непрерывной дробью. Приближение действительного числа подходящими дробями.
   
7. 
   Теорема о единственности представления действительного числа в виде непрерывной дроби.
   
8. 
   Наилучшие приближения.
   
9. 
   Эквивалентные числа. Теорема Серре.
   
10. 
    Квадратичные иррациональности, приведенные квадратичные иррациональности. Конечность множества приведенных иррациональностей с заданным дискриминантом. Дискриминант эквивалентных квадратичных иррациональностей.
    
11. 
    Непрерывная дробь квадратичной иррациональности. Теорема Эйлера-Лагранжа.
    
12. 
    Метод факторизации Ферма и метод Лежандра.
    
13. 
    Мультипликативные функции. Свертка Дирихле. Сумма значений мультипликативной функции по делителям. Формулы для вычисления функций , мультипликативность этих функций.
    
14. 
    Функция Мёбиуса. Формула обращения Мёбиуса. Вычисление значений функции Эйлера.
    
15. 
    Сравнения и их свойства. Полная и приведенная системы вычетов по модулю Теорема Эйлера. Малая теорема Ферма.
    
16. 
    Линейные сравнения. Системы линейных сравнений. Китайская теорема об остатках.
    
17. 
    Теорема Вильсона. Быстрый алгоритм возведения в степень по модулю
    
18. 
    Вероятностный тест проверки простоты числа на основе малой теоремы Ферма. Псевдопростые числа и их свойства. Числа Кармайкла.
    
19. 
    Вероятностный тест Рабина-Миллера. Детерминированный тест Миллера.
    
20. 
    Понятие о криптографии с открытым ключом. Система шифрования RSA.
    
21. 
    Сравнения второй степени по простому модулю. Квадратичные вычеты и невычеты. Критерий Эйлера. Простейшие свойства символа Лежандра.
    
22. 
    Лемма Гаусса о символе Лежандра. Вычисление . Квадратичный закон взаимности.
    
23. 
    Символ Якоби и его свойства.
    
24. 
    Эйлеровы псевдопростые числа и их свойствабмтб. Тест Соловея-Штрассена.
    
25. 
    Полиномиальные сравнения. Лемма Гензеля.
    
26. 
    Количество решений сравнения , .
    
27. 
    Показатель числа по заданному модулю и его свойства. Первообразные корни. Критерий первообразного корня.
    
28. 
    Существование первообразных корней по простому модулю.
    
29. 
    Построение первообразных корней по модулю , где простое нечетное.
    
30. 
    Теорема об отсутствии первообразных корней по модулям, отличным от 2, 4, , простое нечетное. Структура группы при
    
31. 
    Индексы и их свойства. Структура группы . Система Диффи-Хеллмана.