Number Theory в CS

Открытие YouTube запускает алгоритм рекомендаций, который обрабатывает хеш user_id за наносекунды. В партии с шахматным движком позиция хешируется через Зобриста за O(1). Python перемножает 2048-битные числа для RSA - через Karatsuba и NTT. Теория чисел невидимо работает в каждой строчке высоконагруженного кода. FAANG инженеры знают эти алгоритмы наизусть.

• **Rabin-Karp (grep, diff):** поиск паттернов через полиномиальный хеш; используется в grep и текстовых движках
• **Python bigint:** умножение через Karatsuba при n > ~70 цифр; OpenSSL RSA использует NTT
• **Consistent hashing (Dynamo, Cassandra):** virtual nodes хешируются в кольцо; простые числа в размере кольца минимизируют skew

Предварительные знания

• Post-Quantum Cryptography

Хеш-функции и простые числа

Простые числа - скрытые герои хеш-функций. Полиномиальный хеш строки, хеш Зобриста для шахматных позиций, Bloom-фильтры - всё использует простые числа для минимизации коллизий. На собеседованиях FAANG эти техники встречаются постоянно.

**Полиномиальный хеш строки:** hash(s) = (s[0]·b^(n-1) + s[1]·b^(n-2) + ... + s[n-1]) mod p где b - основание (31 или 131), p - большое простое (10^9+7) **Зачем p - простое:** при простом p вероятность коллизии двух разных строк ≈ n/p (по теореме Шварца-Зиппеля). **Хеш Зобриста:** random[piece][square] для каждой (фигура, клетка); итоговый хеш = XOR всех. Мгновенное обновление при ходе. **Почему XOR работает:** хеш Зобриста - частный случай линейного хеша над GF(2) - конечным полем.

На собеседованиях: если задача требует сравнения подстрок за O(1) или обнаружения дублирующихся строк - полиномиальный хеш с двойным хешированием (два разных (b,p)) снижает вероятность коллизии до ~1/10^18.

Генераторы псевдослучайных чисел

random() в Python, rand() в C - это не настоящая случайность. Это Mersenne Twister - детерминированная последовательность, основанная на числах вида 2^n − 1. Для криптографии нужны CSPRNG. Знание internals помогает избегать предсказуемости.

**Линейный конгруэнтный генератор (LCG):** Xₙ₊₁ = (a·Xₙ + c) mod m Период ≤ m. Быстрый, предсказуемый - не для крипто. **Mersenne Twister (MT19937):** Основан на числах Мерсенна: m = 2^19937 − 1 (простое!) Период 2^19937 − 1. Используется в Python random, NumPy. Уязвим: по 624 выходам можно восстановить внутреннее состояние. **CSPRNG:** os.urandom(), secrets.token_bytes() - из /dev/urandom (OS). HMAC_DRBG/CTR_DRBG - стандарты NIST SP 800-90A.

Никогда не используйте random.random() или random.randint() для криптографических целей: генерации ключей, токенов, соли для паролей, nonce для шифрования. Используйте secrets или os.urandom(). Это частая ошибка джунов на собеседованиях.

Быстрая арифметика: Karatsuba и NTT

Перемножение двух n-битных чисел за O(n²) - стандартный алгоритм из школы. Но в криптографии умножаются 2048-битные числа, в ML - полиномы степени 256. Алгоритм Карацубы и NTT (Number Theoretic Transform) снижают сложность до O(n^1.585) и O(n log n).

**Алгоритм Карацубы (1960):** Для умножения двух n-цифровых чисел: вместо 4 рекурсивных умножений - только 3. A·B = (A_hi·2^k + A_lo)(B_hi·2^k + B_lo) = A_hi·B_hi·2^(2k) + (A_hi·B_lo + A_lo·B_hi)·2^k + A_lo·B_lo Средний член: (A_hi+A_lo)·(B_hi+B_lo) − A_hi·B_hi − A_lo·B_lo Сложность: T(n) = 3·T(n/2) → O(n^log₂(3)) ≈ O(n^1.585) **NTT (Number Theoretic Transform):** Дискретное преобразование Фурье над ℤₚ вместо ℂ. Требует: p = k·2ⁿ + 1 (простое), существует примитивный корень ω. Умножение полиномов: O(n log n) - основа Kyber!

Ключевые идеи

• **Полиномиальный хеш:** hash = Σ s[i]·bⁱ mod p; простое p минимизирует коллизии; O(n) построение, O(1) хеш подстроки
• **Mersenne Twister:** период 2^19937−1 но предсказуем по 624 выходам; для крипто - только secrets/os.urandom()
• **Karatsuba:** O(n^1.585) умножение; рекурсия 3T(n/2); Python использует автоматически
• **NTT:** DFT над ℤₚ (p=k·2ⁿ+1); O(n log n) умножение полиномов; сердце Kyber и OpenSSL RSA

Связанные темы

Number Theory in CS показывает, как математика становится производительностью:

• Post-Quantum Cryptography — NTT - ключевая оптимизация умножения полиномов в Kyber
• Тесты простоты — Размер хеш-таблицы - ближайшее простое к N; Miller-Rabin проверяет кандидатов
• Number Theory на собеседовании — Полиномиальный хеш и Karatsuba - типичные темы FAANG-собеседований

Вопросы для размышления

• Python bigint автоматически переключается с O(n²) на Karatsuba примерно при 70+ цифрах. Почему не всегда использовать Karatsuba, даже для маленьких чисел?
• Хеш Зобриста использует XOR - линейную операцию над GF(2). Почему линейность не делает его уязвимым к атакам на основе линейной алгебры?
• Consistent hashing в Cassandra размещает virtual nodes в кольцо хешей. Какие свойства модуля p кольца влияют на равномерность распределения узлов?

Связанные уроки

• alg-01-big-o