Discrete Math в CS

Когда решаете задачу на интервью в Google и понимаете, что это NP-полная - экономите час попыток найти полиномиальное решение. Когда настраиваете TLS - выбираете криптографические примитивы, безопасность которых доказана через теорию групп. Когда проектируете кеш для миллиарда URL - считаете false positive rate Bloom Filter. Это и есть дискретная математика в FAANG.

• **Google Safe Browsing:** Bloom Filter с ~8 битами/URL для проверки опасных сайтов без отправки URL на сервер при каждом запросе
• **TLS 1.3:** ECDH для обмена ключами (дискретный логарифм), Miller-Rabin для генерации RSA-ключей, SHA-256 для хеширования
• **Компилятор LLVM:** раскраска графа регистров (NP-полная задача) решается жадным приближением - основа кодогенерации
• **Apache Cassandra:** Bloom Filter для проверки существования строки перед чтением диска, снижает I/O в 10-100 раз

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

• Random Variables

Классы сложности: P, NP, NP-полнота

Google использует алгоритм P-vs-NP граничного типа: RSA-2048 стоит на твёрдости факторизации - задача, для которой квантовый компьютер с 4000 кубитами справится за минуты. Теория сложности отвечает на вопрос: какие задачи принципиально трудно решить? Классы P и NP определяют границу между «эффективно решаемым» и «возможно, нет». Понимание этой границы критично при выборе алгоритмов для production-систем.

**Классы сложности:** - **P:** задачи, решаемые за полиномиальное время O(n^k). Сортировка, поиск кратчайшего пути, умножение матриц. - **NP:** задачи, решение которых можно верифицировать за полиномиальное время. Включает P. - **NP-полные:** наиболее трудные задачи в NP: если одну решить за полиномиальное время, решатся все NP-задачи. - **P = NP?** - открытый вопрос, $1 млн от Clay Institute. Большинство исследователей полагает P ≠ NP.

На практике NP-полные задачи решаются приближёнными алгоритмами (approximation algorithms), эвристиками или ILP-солверами (CPLEX, Gurobi). Компиляторы используют жадную раскраску графа (не оптимальную) для распределения регистров. TSP решают эвристиками типа 2-opt или симулированным отжигом.

Если на интервью встретили задачу, похожую на NP-полную - не пытайтесь найти точное полиномиальное решение. Правильный ответ: «это похоже на задачу X (NP-полная), поэтому мы используем приближение / эвристику / ILP-солвер».

Вероятностные алгоритмы: Miller-Rabin

Вероятностные алгоритмы используют случайность для достижения быстрых результатов с высокой вероятностью правильности. Тест Миллера-Рабина - вероятностный тест простоты, используемый в OpenSSL, Python, Java для генерации криптографических ключей.

**Тест Миллера-Рабина (основа малой теоремы Ферма):** Пусть n нечётное, n-1 = 2^s · d. Выбираем случайное a (свидетель). n - вероятно простое, если: - a^d ≡ 1 (mod n), или - a^(2^r·d) ≡ -1 (mod n) для некоторого r ∈ [0, s-1] Если условие не выполнено, n составное (ложь невозможна). При k независимых свидетелях P(ошибки) < 4^(-k).

**Категории вероятностных алгоритмов:** - **Las Vegas:** всегда правильный ответ, случайное время. Пример: randomized quicksort. - **Monte Carlo:** фиксированное время, возможна ошибка с малой вероятностью. Пример: Miller-Rabin. - **RP:** Monte Carlo с ошибкой только в одну сторону (false positive или false negative, не оба).

**Почему Miller-Rabin предпочтительнее детерминированного AKS в production:** AKS теоретически полиномиален, но константы в O(log^6 n) огромны. Miller-Rabin с k=40 раундами быстрее на практике, а P(ошибки) < 4^(-40) ≈ 10^(-24) - меньше вероятности аппаратной ошибки.

RSA и Diffie-Hellman: математика под капотом

RSA и Diffie-Hellman - два фундаментальных криптографических протокола, основанных на дискретной математике. RSA опирается на сложность факторизации больших чисел, DH - на сложность дискретного логарифма в мультипликативной группе.

**RSA (Rivest-Shamir-Adleman, 1977):** 1. Генерация: выбрать простые p, q; n=p·q; φ(n)=(p-1)(q-1) 2. Публичный ключ: e такой, что gcd(e, φ(n))=1 (обычно e=65537) 3. Приватный ключ: d = e⁻¹ mod φ(n) (расширенный алгоритм Евклида) 4. Шифрование: c = m^e mod n 5. Дешифрование: m = c^d mod n (работает по малой теореме Ферма) **Безопасность:** нет эффективного алгоритма факторизации n=p·q при |p|,|q|≈1024 бит.

**Diffie-Hellman (1976):** первый протокол обмена ключами через открытый канал. Алиса и Боб публично публикуют (p, g), затем обмениваются g^a mod p и g^b mod p. Общий секрет g^(ab) mod p вычисляется обоими, но не перехватчиком: для этого нужно решить задачу дискретного логарифма.

**Что использует TLS 1.3:** ECDH (Elliptic Curve Diffie-Hellman) с кривой X25519 или P-256 для ephemeral ключей + AES-256-GCM для шифрования данных + HMAC-SHA-256 для MAC. RSA или ECDSA - только для подписи сертификата. Понимание математики позволяет правильно выбирать параметры и оценивать безопасность.

Bloom Filter: вероятность + хеширование

Bloom Filter - вероятностная структура данных для проверки принадлежности элемента множеству. Использует k хеш-функций и битовый массив размера m. Ложные отрицания невозможны. Ложные положительные возможны с вероятностью, которую можно точно вычислить.

**Вероятность ложного положительного (false positive rate):** После добавления n элементов в массив размера m с k хеш-функциями: p_fp ≈ (1 - e^(-kn/m))^k **Оптимальное k** при заданных m и n: k* = (m/n) · ln(2) ≈ 0.693 · (m/n) **Оптимальный размер m** для целевого fp_rate ε: m = -n · ln(ε) / (ln 2)²

Bloom Filter применяется там, где ложное положительное дёшево, а ложное отрицательное недопустимо. Примеры: CDN проверяет кешируемость URL (false positive = лишнее обращение к origin, ok), Chrome Safe Browsing (false positive = лишний сетевой запрос, ok), HBase/Cassandra (false positive = лишнее чтение диска, ok).

Стандартные параметры для практики: fp_rate=1% → m ≈ 9.6 бит/элемент, k=7 хешей. fp_rate=0.1% → m ≈ 14.4 бит/элемент, k=10 хешей. Уменьшение fp_rate в 10 раз требует увеличения m примерно в 1.5 раза.

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

• **P vs NP:** P - быстро решаемые, NP - быстро верифицируемые. NP-полные задачи (3-SAT, TSP, раскраска) - наиболее трудные в NP.
• **Miller-Rabin:** вероятностный тест простоты с P(ошибки) < 4^(-k). Используется в OpenSSL, Python, Java для генерации RSA-ключей.
• **RSA:** безопасность на факторизации n=p·q. Ключи: e·d ≡ 1 (mod φ(n)). Шифрование/дешифрование через быстрое возведение в степень.
• **Diffie-Hellman:** обмен ключами через открытый канал. Безопасность на дискретном логарифме в Z_p* или на эллиптической кривой.
• **Bloom Filter:** битовый массив + k хешей. Нет false negatives. P(false positive) точно вычислима. Используется в Chrome, Cassandra, Redis.

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

Эта тема объединяет все разделы курса в практические CS-приложения:

• Группы и кольца — RSA и DH строятся на группах Z_p* и GF(2^8); математическая основа AES
• Случайные величины — Анализ вероятностных алгоритмов: ожидаемое время работы, хвостовые оценки
• Discrete Math на собеседовании — NP-полнота, вероятностные алгоритмы и Bloom Filter - типичные темы FAANG system design

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

• Если P = NP (хотя это маловероятно), что произойдёт с безопасностью RSA и других криптосистем, основанных на предполагаемой сложности задач?
• Miller-Rabin с k=40 раундами используется в OpenSSL. P(ошибки) < 4^(-40) ≈ 10^(-24). Почему этого достаточно, и что было бы, если бы использовался k=1?
• проектируете систему дедупликации для 10 миллиардов URL (веб-краулер). Почему Bloom Filter с fp_rate=0.1% предпочтительнее хеш-сета? Рассчитайте, сколько памяти нужно каждому подходу.

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

• alg-01-big-o