Теория чисел (27 мая)

  1. Разделяй и властвуй
    1. Системы счисления: перевод из одной в другую за O(nlog2n)
  2. Простые числа
    1. Решето Эратосфена за O(NloglogN)
    2. Решето Эратосфена за O(N)
    3. Количество делителей числа, вычисление решетом для всех чисел от 1 до N
  3. Вычисление по модулю
    1. Сложение, вычитание.
    2. Умножение − через сложение, с помощью вещественных
    3. Деление (обратное) − возведение в степень, расширенный Евклид
    4. КТО
    5. C(n, k) по не простому модулю
  4. RSA.
    1. φ(n) = количество чисел взаимнопростых с данным
    2. Кодирование: p, q → n=pq, phi=(p-1)(q-1), e=rand():(e,phi)=1 ⇒ x → xe(phi)
    3. Декодирование: de=1(phi) ⇒ xed=xed=xk*phi+1=x(n)
    4. Взлом ⇔ факторизации числа
  5. Диофантовы уравнения
    1. Существование решение, количество решений, класс решений
  6. Первообразный корень
    1. Поиск
    2. Дискретное логарифмирование
    3. Возведение в степень
    4. Извлечение корня
    5. Извлечение корня квадратного за лог (квадратные уравнения)
  7. Факторизация
    1. p-Эвристика полларда
    2. тест Ферма, алгоритм Крайчик + квадратичное решето + Wiedemann
    3. оптимальное время: exp((logn)1/3)
  8. Проверка на простоту
    1. Наивная проверка
    2. Тест Ферма
    3. Тест Миллера-Рабина
  9. [не успеем] Функция Мёбиуса, формула включения-исключения
  10. [не успеем] Поиск корней многочлена за O(n2logn)
  11. [не успеем] min x <-> max x <-> x=0