Факторизация (22-е мая 2019)

  1. Из прошлого
    1. Паросочетания
      1. VEα − хранить p[] только для остовного дерева bfs
      2. dfs позволяет искать LCA(v, u) за O(1) − это будет или base[v], или base[u]
      3. Двойственная задача
    2. Матричные игры
      1. Детерминированные стратегии. Вероятностные стратегии.
      2. Оптимальная вероятностная стратегия: mini(∑aijxj) → max
      3. Записываем задачу через LP для первого и второго игроков. Проверяем, что задача второго двойственна задаче первого.
      4. ♥ Теорема Нэша для матричных игр (сильная теорема двойственности для уже записанных задач LP)

  2. Метод Крайчика
    1. Тест ферма: u2 - v2 = 0, u2 - v2 ≡ 0 (mod n)
    2. xi = floor(sqrt(n)) + i, yi = xi2 - n
    3. Алгоритм: найти z = ∏yij, являющееся точным квадратом, и скормить тесту Ферма ∏xij2 и z.
    4. Число точный квадрат ⇔ в разложении все степени чётны, выберем b-гладкие yi, факторизуем, полученные битовые вектора скормим Гауссу.
    5. Псевдокод: фиксируем число простых k (b = primek), перебираем yi, b-гладкие скармливаем инкрементальному Гауссу с вероятностью 1/2 до первой линейной зависимости.
    6. Оптимизации
      1. Гаусс → Гаусс для разреженных матриц или даже Видеман
      2. Факторизация b-гладких yi → для каждого из простых решили квадратное уравнение (квадратичное решето)
      3. Итоговое время работы O*(k2 + m), где (*) − loglog-и.
    7. Итоговое время алгоритма: при k↑ m↓, выбираем k2 = m, получаем esqrt(lognloglogn) = L(1/2, 1)
    8. Решения лучше: L(1/3, (32/9)1/3) даёт SNFS (Special number field sieve)