Алгебра и теория чисел :: занятие 02 (16.02.2010)

Занятие 1 (16.02.2010)
Практические задачи. Основные алгоритмы теории чисел
Лекция. (Теория) Основные элементы теории чисел
Лекция. (Практика) Основные алгоритмы теории чисел

Занятие 1 (16.02.2010)
Основные алгоритмы теории чисел ps pdf
divmod.Деление остатков по модулюps pdf
crt.Китайская теорема об остаткахps pdf
totient.Функция Эйлераps pdf
power.Возведение в степень по модулюps pdf
(Теория) Основные элементы теории чисел
План лекции
  1. Сравнения
    1. Сравнение чисел по модулю. Арифметика по модулю
    2. Полная и приведенная система вычетов
    3. Отсутствие делителей нуля в приведенной системе вычетов
    4. Решение линейных сравнений по модулю, деление остатков
    5. Китайская теорема об остатках, некоструктивное доказательство
    6. Малая теорема Ферма
    7. Теорема Вильсона
  2. Теоретико-числовые функции
    1. Функция Эйлера (totient function), мультипликативность функции Эйлера
    2. Теорема Эйлера
    3. Число делителей, сумма делителей, функция Мёбиуса
    4. Свертка Дирихле мультипликативных функций
      • Теорема о мультипликативности свертки Дирихле
      • Теорема об ассоциативности и коммутативности свертки Дирихле
      • Теорема о существовании обратного элемента относительно свертки Дирихле
      • Формула обращения Мёбиуса: обратный элемент для функции Мёбиуса
(Практика) Основные алгоритмы теории чисел
План лекции
  1. Китайская теорема об остатках, конструктивное доказательство
  2. Вычисление мультипликативных функций с помощью решета Эратосфена
  3. Быстрое возведение в степень
    1. Метод right-left
    2. Метод left-right
  4. Умножение по Монтгомери