Number Theory in Computer Science

Opening YouTube triggers the recommendation algorithm to hash a user ID in nanoseconds. In a chess engine match, each position is Zobrist-hashed in O(1). Python multiplies 2048-bit RSA numbers using Karatsuba and NTT under the hood. Number theory works invisibly in every line of high-performance code. FAANG engineers know these algorithms cold.

• **Rabin-Karp (grep, diff):** pattern search via polynomial hashing; used in grep, text editors, and plagiarism detection
• **Python bigint:** automatically switches to Karatsuba for n > ~70 digits; OpenSSL RSA uses NTT for Montgomery multiplication
• **Consistent hashing (Dynamo, Cassandra):** virtual nodes hashed onto a ring; prime ring size minimizes load skew

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

• Post-Quantum Cryptography

Hash Functions and Primes

Primes are the hidden heroes of hash functions. Polynomial string hashing, Zobrist hashing for chess positions, Bloom filters-all use primes to minimize collisions. FAANG interviews touch these techniques constantly.

**Polynomial rolling hash:** hash(s) = (s[0]·b^(n-1) + s[1]·b^(n-2) + ... + s[n-1]) mod p where b is a base (31 or 131) and p is a large prime (10^9+7) **Why prime p:** for a prime modulus, the collision probability for two distinct strings is ≈ n/p (Schwartz-Zippel lemma). **Zobrist hashing:** random[piece][square] for each (piece, square) pair; board hash = XOR of all occupied entries. O(1) update per move. **Why XOR works:** Zobrist is a linear hash over GF(2)-a finite field.

Interview pattern: when a problem requires O(1) substring comparison or deduplication of strings, use double hashing (two independent (b,p) pairs). Collision probability drops to ~1/10^18-negligible for any practical input.

Pseudo-Random Number Generators

Python's random() and C's rand() are not truly random. They implement the Mersenne Twister-a deterministic sequence whose period is a Mersenne number 2ⁿ−1. For cryptography, a CSPRNG is required. Understanding the internals helps avoid predictability bugs.

**Linear Congruential Generator (LCG):** Xₙ₊₁ = (a·Xₙ + c) mod m Period ≤ m. Fast but directly predictable. **Mersenne Twister (MT19937):** Based on Mersenne number: m = 2^19937 − 1 (which is prime!) Period 2^19937 − 1. Used in Python random, NumPy. Vulnerability: from 624 consecutive outputs, the full state is recoverable. **CSPRNG:** os.urandom(), secrets module-draws from /dev/urandom (OS entropy pool). HMAC_DRBG/CTR_DRBG-NIST SP 800-90A standards.

Never use random.random() or random.randint() for key generation, authentication tokens, password salts, or encryption nonces. Use secrets or os.urandom() instead. This is a common junior-level mistake that appears frequently in security audits.

Fast Arithmetic: Karatsuba and NTT

Multiplying two n-digit numbers in O(n²) is the schoolbook approach. But cryptography multiplies 2048-bit integers, and machine learning multiplies degree-256 polynomials. Karatsuba and NTT (Number Theoretic Transform) cut the cost to O(n^1.585) and O(n log n).

**Karatsuba multiplication (1960):** Instead of 4 recursive multiplications: only 3. A·B where A = A_hi·2^k + A_lo: z0 = A_lo·B_lo z2 = A_hi·B_hi z1 = (A_hi+A_lo)·(B_hi+B_lo) − z2 − z0 A·B = z2·2^(2k) + z1·2^k + z0 Complexity: T(n) = 3T(n/2) → O(n^log₂3) ≈ O(n^1.585) **NTT (Number Theoretic Transform):** Discrete Fourier Transform over ℤₚ instead of ℂ. Requires: prime p = k·2ⁿ + 1 with a primitive root of order 2ⁿ. Polynomial multiplication: O(n log n)-the core of Kyber.

Key Ideas

• **Polynomial hash:** hash = Σ s[i]·bⁱ mod p; prime p minimizes collisions; O(n) build, O(1) substring hash query
• **Mersenne Twister:** period 2^19937−1 but state is recoverable from 624 outputs; use secrets/os.urandom() for crypto
• **Karatsuba:** O(n^1.585) integer multiply via 3 recursive half-size multiplications; Python uses it automatically
• **NTT:** DFT over ℤₚ (p=k·2ⁿ+1); O(n log n) polynomial multiply; core of Kyber and OpenSSL RSA

Related Topics

Number theory in CS shows how pure mathematics becomes performance:

• Post-Quantum Cryptography — NTT is the key polynomial multiplication optimization inside Kyber
• Primality Tests — Finding the nearest prime to N for hash table sizing uses Miller-Rabin
• Number Theory in Interviews — Polynomial hashing and Karatsuba are recurring FAANG interview topics

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

• Python's bigint automatically switches from O(n²) to Karatsuba at about 70 digits. Why not always use Karatsuba, even for tiny numbers?
• Zobrist hashing uses XOR-a linear operation over GF(2). Why doesn't linearity make it vulnerable to linear-algebra attacks on hash collisions?
• Consistent hashing in Cassandra places virtual nodes onto a hash ring. What properties of the ring's modulus p affect how evenly nodes are distributed?

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

• alg-01-big-o