Факторизация (3-е апреля 2024)

  1. ♥ Метод Крайчика (алгоритм Диксона '1981)
    1. Тест ферма: u2 - v2 = 0, u2 - v2 ≡ 0 (mod n)
    2. xi = ceil(sqrt(n)) + i, yi = xi2 - n
    3. Алгоритм: найти z = ∏yij, являющееся точным квадратом, и скормить тесту Ферма ∏xij2 и z.
    4. Число точный квадрат ⇔ в разложении все степени чётны, выберем b-гладкие yi, факторизуем, полученные битовые вектора скормим Гауссу.
    5. Псевдокод: фиксируем число простых k (b = primek), перебираем yi, b-гладкие скармливаем инкрементальному Гауссу. Если очередная строка = линейная комбинация предыдущих, вызываем тест Ферма.
    6. Время работы: O(k3/w + mk)

  2. Оптимизируем Метод Крайчика в квадратичное решето (Carl Pomerance '1981)
    1. Гаусс → алгоритм Видеман за O(n * "число не нулевых элементов")
    2. Факторизация b-гладких yi → для каждого из простых решили квадратное уравнение (квадратичное решето)
    3. Извлечение корня: за O(p), за O(p1/2), за O(logp)
    4. Итоговое время работы O*(k2 + m), где (*) множитель, учитывающий длинность чисел.
    5. L-notation: L(a, b) = exp(a*logb*loglog1-b).
    6. Итоговое время алгоритма: при k↑ m↓, выбираем k2 = m, получаем esqrt(logn * loglogn) = L(1/2, 1)
    7. Решения лучше: L(1/3, (32/9)1/3) даёт SNFS (Special number field sieve), GNFS (general number field sieve)

  3. Матричные игры
    1. Детерминированные стратегии. Вероятностные стратегии.
    2. ♥ Оптимальная вероятностная стратегия: mini(∑aijxj) → max
    3. Записываем задачу через LP для первого и второго игроков. Проверяем, что задача второго двойственна задаче первого.
    4. Теорема Нэша для матричных игр (сильная теорема двойственности для уже записанных задач LP)

  4. [skipped] SDP
    1. [skipped] Упражнение: пересечение и полупространств и эллипсоидов методом эллипсоидов
    2. [skipped] Определение задачи SDP, связь с LP
    3. [skipped] Решение SDP методом Эллипсоидов
    4. [skipped] MAX-CUT : определение задачи, 0.5*OPT решение
    5. [skipped] MAX-CUT : сведение к SDP, получение OPT(SDP) ≥ OPT(MAX-CUT)
    6. [skipped] Релаксация решения SDP к решению MAX-CUT