Теория чисел
Теория чисел в алгоритмах
Когда Python умножает два числа по 10000 цифр, он использует теорему о малой теореме Ферма и примитивные корни из единицы. NTT - это магия теории чисел в продакшне: задача, которая выглядит как O(N^2), решается за O(N log N) благодаря тому, что в Zp существуют корни из единицы нужного порядка.
- **Python int multiplication:** для чисел > ~2000 цифр Python использует FFT/NTT-based умножение
- **Криптография:** NTT - основа схемы CRYSTALS-Kyber (NIST post-quantum стандарт), где умножение полиномов mod q центральная операция
- **Соревновательное программирование:** сотни задач на Codeforces/ICPC требуют полиномиального умножения через NTT
Предварительные знания
Примитивные корни и корни из единицы mod p
RSA-2048 (стандарт TLS 2024) использует Miller-Rabin тест для primality testing: 99.99% вероятность за 50 итераций. **NTT работает над Zp**, где p - специальное простое вида p = c * 2^k + 1. В этом поле существуют **корни из единицы** порядка 2^k - аналоги комплексных e^(2πi/n). Примитивный корень g mod p играет роль e^(2πi/N) в обычном DFT.
Для NTT длиной N нужно p = c*2^k+1 с N | 2^k. Популярные NTT-простые: p = 998244353 = 119 * 2^23 + 1 (g=3), поддерживает NTT до длины 2^23. p = 469762049 = 7 * 2^26 + 1 (g=3). p = 1004535809 = 479 * 2^21 + 1 (g=3). Все fit в int32 без overflow при умножении через int64.
Почему для NTT нужно простое p вида c*2^k+1, а не произвольное простое?
Алгоритм NTT: FFT над Zp
**NTT (Number Theoretic Transform)** - это DFT, где комплексные числа заменены элементами Zp, а мнимая единица i заменена примитивным корнем из единицы. Алгоритм Cooley-Tukey (butterfly) работает без изменений: O(N log N) операций mod p, только целочисленная арифметика.
FFT: работает над C; страдает от ошибок округления; результаты вещественные - нужно округлять. NTT: работает над Zp; абсолютно точный результат; подходит для полиномов с целыми коэффициентами; нет ошибок; быстрее на практике (нет float). Ограничение NTT: коэффициенты результата берутся mod p - если они большие, нужно использовать несколько простых (CRT).
В чём главное преимущество NTT перед FFT для умножения полиномов с целыми коэффициентами?
Умножение полиномов за O(N log N)
**Умножение полиномов** A(x) * B(x) наивным способом - O(N^2). С NTT: вычислить NTT(A) и NTT(B), перемножить поточечно, применить обратный NTT - итого O(N log N). Этот приём - основа быстрого умножения больших чисел.
NTT(A * B) = NTT(A) . NTT(B) (поточечное произведение). Это означает: умножение полиномов = NTT + поточечное умножение + INTT. Для больших коэффициентов (превышающих MOD) применяем несколько простых p1, p2, p3 и восстанавливаем через CRT (Chinese Remainder Theorem).
Если коэффициенты результата умножения полиномов могут превышать MOD=998244353, как получить точный ответ?
NTT в соревновательном программировании и продакшне
NTT используется повсеместно: умножение больших чисел (GMP, Python int), полиномиальные алгоритмы на деревьях, задачи подсчёта в DP. Многие задачи, которые кажутся O(N^2) DP, решаются за O(N log N) через полиномиальное умножение.
Число = полином от базы B=10^4. Число с N цифрами = полином степени N/4. Умножение двух N-значных чисел: O(N log N) через NTT. Python: int * int использует алгоритм Карацубы (O(N^1.585)) или FFT для очень больших; GMP использует NTT начиная с ~2000 цифр. Библиотека NTL: промышленная реализация NTT.
Какова сложность умножения двух N-значных чисел с использованием NTT?
Ключевые идеи
- **NTT-простое** p = c*2^k+1 гарантирует существование корней из единицы порядка 2^m для NTT длиной 2^m
- **NTT = FFT над Zp:** те же butterfly-операции, но mod p; точный целочисленный результат без float-ошибок
- **Теорема свёртки:** NTT(A*B) = NTT(A) . NTT(B); умножение полиномов за O(N log N)
- **CRT для больших коэффициентов:** вычислить mod нескольких простых, восстановить точный ответ
Связанные темы
NTT соединяет модулярную арифметику с алгоритмами:
- Модулярная арифметика — NTT работает в Zp; быстрое возведение в степень mod p - ключевая операция
- Теоремы Ферма и Эйлера — Малая теорема Ферма используется для вычисления обратного элемента mod p в INTT
- Post-Quantum Cryptography — CRYSTALS-Kyber (NIST PQC стандарт) использует NTT для умножения полиномов над Zq
Вопросы для размышления
- NTT работает только над Zp, но результат умножения полиномов - над Z. Как именно CRT позволяет восстановить точный ответ? При каких условиях это работает?
- Алгоритм Карацубы и NTT оба быстрее O(N^2). Когда выгоднее использовать каждый из них?
- Схема CRYSTALS-Kyber использует NTT для умножения полиномов mod q=3329. Найдите: является ли 3329 NTT-friendly простым? Какую максимальную длину NTT оно поддерживает?