Теория чисел ТЕОРИЯ ЧИСЕЛ
Программа курса
(ОКН, 3 семестр, 2002/03 уч.г.)

  1. Теория делимости. Основные понятия и теоремы (делитель, основное свойство, деление с остатком).
  2. Наибольший общий делитель и алгоритм Евклида (свойства наибольшего общего делителя, расширенный алгоритм Евклида, взаимнопростые числа).
  3. Линейные диофантовы уравнения с двумя неизвестными.
  4. Простые числа (определение и простейшие свойства, теорема Евклида).
  5. Распределение простых чисел (теорема Чебышева, цепочки составных, решето Эратосфена).
  6. Основная теорема арифметики (каноническое разложение, выражения для наибольшего общего делителя и наименьшего общего кратного).
  7. Цепные дроби (основные определения и свойства, разложение чисел в цепную дробь и связь с алгоритмом Евклида).
  8. Вычисление подходящих дробей (вывод рекуррентных соотношений, связь с расширенным алгоритмом Евклида).
  9. Свойства подходящих дробей.
  10. Континуанты (определение и основные свойства, связь с цепными дробями).
  11. Анализ алгоритма Евклида (теорема Ламэ и ее следствие).
  12. Приближение действительных чисел подходящими дробями.
  13. Целая и дробная части числа (показатель простого в факториале, число целочисленных точек под непрерывной кривой, комбинаторная формула площади многоугольника).
  14. Мультипликативные функции и их свойства.
  15. Примеры мультипликативных функций (число делителей, сумма делителей, функция Мёбиуса).
  16. Функция Эйлера.
  17. Сравнения и их свойства.
  18. Полная и приведенная система вычетов.
  19. Теоремы Эйлера и Ферма и их следствия.
  20. Сравнения первой степени (определение, решение с помощью цепных дробей, метод Эйлера).
  21. Китайская теорема об остатках.
  22. Сравнения любой степени по простому модулю (две основные леммы).
  23. Теорема Вильсона.
  24. Сравнения любой степени по составному модулю (теорема о числе решений).
  25. Сравнения любой степени по составному модулю (процесс сведения).
  26. Двучленные сравнения любой степени.
  27. Двучленные сравнения второй степени (определение, квадратичные вычеты, лемма о числе решений двучленного сравнения, лемма о приведенной системе вычетов).
  28. Критерий Эйлера.
  29. Свойства символа Лежандра.
  30. Символа Лежандра. Лемма Гаусса.
  31. Значение символа Лежандра (2/p).
  32. Закон взаимности квадратичных вычетов.
  33. Символ Якоби. Свойства символа Якоби. Обобщение квадратичного закона.
  34. Алгоритмы вычисления символа Лежандра.
  35. Двучленные сравнения второй степени по модулю степени нечетного простого числа.
  36. Двучленные сравнения второй степени. Алгоритм сведения для сравнений по модулю 2a.

Рекомендуемая литература для подготовки к экзамену
  1. Виноградов И.М. Основы теории чисел.
  2. Бухштаб А.А. Теория чисел.
  3. Сизый С.В. Лекции по теории чисел.

Дополнительная литература
для дальнейшего самостоятельного изучения
  1. Боревич З.И., Шафаревич И.Р. Теория чисел. М: Наука, гл.ред.физ.-мат.лит. 1985. 504 с.
  2. Коблиц Н. Курс теории чисел и криптографии. Пер. с англ. М.: Науч. изд-во ТВП, 2001. 260 с.
  3. Коутинхо С. Введение в теорию чисел и алгоритм RSA
  4. Кнут Д. Искусство программирования. Т2. Получисленные алгоритмы.

Программу подготовил к.т.н., доцент
кафедры инфомационной безопасности Д.Н. Лавров


File translated from TEX by TTH, version 2.25.
On 14 Dec 2002, 23:56.