Алгебра и теория чисел: целочисленная арифметика, простые числа

• Алгоритмы теории чисел

Простые числа.
  Проверка простоты - за полином.
  Факторизация - за экспоненту.
  Упоминание RSA.
Вычисления по модулю.
  Лемма (a + b) mod c = (a mod c + b mod c) mod c.
  Лемма (a * b) mod c = (a mod c * b mod c) mod c.
Задача: a * b mod c, оставаясь в целом типе.
  Десятичное умножение в столбик.
  Двоичное умножение в столбик.
  Идея со сложением нужных из a, 2 a, 4 a, 8 a, ... .
  Медленное умножение.
  Код на Си и на Паскале.
Задача: a ^ b mod c, оставаясь в целом типе.
  Сложение -> умножение - то же, что и умножение -> возведение в степень.
  Идея с перемножением нужных из a, a^2, a^4, a^8, ... .
  Быстрое возведение в степень.
  Код на Си.
Мотивационная задача: проверка числа на простоту.
  Периоды a, a^2, a^3, a^4, a^5, ... mod p на примере p = 7.
  Малая теорема Ферма.
  Функция Эйлера.
  Теорема Эйлера - обобщение теоремы Ферма.
  Лемма: \phi (m) = m - 1 равносильно тому, что m простое.
  Тест Ферма.
  Числа Кармайкла (минимальное - 561).
  Корни из единицы по модулю m.
  Лемма: m простое => корни из единицы только +-1.
  Тест Миллера-Рабина.
Матрицы.
  Числа Фибоначчи.
  Получение вектора (F_{n}, F_{n - 1}) из вектора (F_{n - 1}, F_{n - 2}).
  Матрицы и правила умножения матриц.
  Умножение матрицы ((1, 1), (1, 0)) на себя несколько раз справа и слева.
  Наблюдение за тем, как в матрице получаются числа Фибоначчи.
  Одно умножение на матрицу - это переход (n - 1) -> n.
  Получение числа Фибоначчи с большим номером по модулю.
  Быстрое возведение матрицы в степень.
  Последовательность G_{n} = G_{n - 1} + 2 G_{n - 3} и соответствующая матрица.
  H_{n} = H_{n - 1} + 2 H_{n - 3}, добавляем + 1, добавляем + n.