Part 6: Number Theory and Cryptography

Part of the Mathematics for Programming 101 Series

The Security Incident That Taught Me Number Theory

I was reviewing a JWT token implementation. The tokens were predictable.

Someone had used:

token_id = int(time.time())  # Timestamp as token ID

I could predict future tokens. Generate a valid token for 10 seconds in the future, use it before it's issued.

The fix required understanding modular arithmetic and prime numbers:

import secrets

# Cryptographically secure random
token_id = secrets.randbelow(2**128)  # 128-bit random number

# Or use prime field arithmetic
p = 2**127 - 1  # Mersenne prime
token_id = secrets.randbelow(p)

That's when I realized: Number theory isn't abstract mathematics—it's the foundation of security in every system we build.

Modular Arithmetic: Clock Mathematics

The Basics

Modular arithmetic is like a clock: numbers wrap around at a certain value (the modulus).

# Modulo operator: remainder after division
print(f"17 mod 5 = {17 % 5}")  # 2
print(f"23 mod 7 = {23 % 7}")  # 2
print(f"8 mod 3 = {8 % 3}")    # 2

# Clock arithmetic: 3 hours after 11 o'clock
current_hour = 11
hours_later = 4
new_hour = (current_hour + hours_later) % 12
print(f"{hours_later} hours after {current_hour} = {new_hour}")  # 3

# Properties of modular arithmetic
a, b, m = 17, 23, 5

# (a + b) mod m = ((a mod m) + (b mod m)) mod m
result1 = (a + b) % m
result2 = ((a % m) + (b % m)) % m
print(f"\n(17 + 23) mod 5 = {result1}")
print(f"((17 mod 5) + (23 mod 5)) mod 5 = {result2}")
assert result1 == result2

# (a * b) mod m = ((a mod m) * (b mod m)) mod m
result1 = (a * b) % m
result2 = ((a % m) * (b % m)) % m
print(f"\n(17 * 23) mod 5 = {result1}")
print(f"((17 mod 5) * (23 mod 5)) mod 5 = {result2}")
assert result1 == result2

Real Application: Hash Tables

Hash tables use modular arithmetic to map keys to buckets:

class SimpleHashTable:
    """Hash table using modular arithmetic"""
    
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]  # Chaining for collisions
    
    def _hash(self, key):
        """Hash function using modular arithmetic"""
        # Simple hash: sum of character codes mod table size
        if isinstance(key, str):
            hash_value = sum(ord(c) for c in key)
        else:
            hash_value = hash(key)
        
        return hash_value % self.size
    
    def insert(self, key, value):
        """Insert key-value pair"""
        index = self._hash(key)
        
        # Check if key already exists
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)  # Update
                return
        
        # Add new entry
        self.table[index].append((key, value))
    
    def get(self, key):
        """Retrieve value by key"""
        index = self._hash(key)
        
        for k, v in self.table[index]:
            if k == key:
                return v
        
        raise KeyError(key)
    
    def display(self):
        """Show hash table structure"""
        for i, bucket in enumerate(self.table):
            if bucket:
                print(f"Bucket {i}: {bucket}")

# Example
ht = SimpleHashTable(size=5)
ht.insert("apple", 1)
ht.insert("banana", 2)
ht.insert("cherry", 3)
ht.insert("date", 4)

print("Hash Table Contents:")
ht.display()

print(f"\nGet 'banana': {ht.get('banana')}")

Modular Exponentiation

Computing large powers efficiently (crucial for cryptography):

def modular_exp_naive(base, exp, mod):
    """Naive approach: compute base^exp, then mod
    Problem: base^exp can be astronomically large"""
    return (base ** exp) % mod

def modular_exp_efficient(base, exp, mod):
    """
    Efficient modular exponentiation
    Uses property: (a * b) mod m = ((a mod m) * (b mod m)) mod m
    
    Time complexity: O(log exp)
    """
    result = 1
    base = base % mod
    
    while exp > 0:
        # If exp is odd, multiply base with result
        if exp % 2 == 1:
            result = (result * base) % mod
        
        # exp must be even now
        exp = exp >> 1  # exp = exp // 2
        base = (base * base) % mod
    
    return result

# Compare performance
import time

base, exp, mod = 12345, 67890, 10007

# Efficient version (works for large numbers)
start = time.time()
result = modular_exp_efficient(base, exp, mod)
efficient_time = time.time() - start

print(f"Efficient: {base}^{exp} mod {mod} = {result}")
print(f"Time: {efficient_time*1000:.4f}ms")

# Built-in (uses same algorithm)
start = time.time()
result_builtin = pow(base, exp, mod)
builtin_time = time.time() - start

print(f"Built-in pow: {result_builtin}")
print(f"Time: {builtin_time*1000:.4f}ms")

assert result == result_builtin

Prime Numbers: Building Blocks of Cryptography

Testing for Primes

def is_prime_naive(n):
    """Naive primality test: O(n)"""
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

def is_prime_optimized(n):
    """Optimized: only check up to sqrt(n): O(√n)"""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    # Check odd divisors up to sqrt(n)
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    
    return True

def is_prime_miller_rabin(n, k=5):
    """
    Miller-Rabin primality test (probabilistic)
    Much faster for large numbers
    k = number of rounds (higher = more accurate)
    """
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    
    # Write n-1 as 2^r * d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    
    # Witness loop
    import random
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        
        if x == 1 or x == n - 1:
            continue
        
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    
    return True

# Compare performance
import time

test_number = 982451653  # Large prime

start = time.time()
result = is_prime_optimized(test_number)
time_optimized = time.time() - start

start = time.time()
result_mr = is_prime_miller_rabin(test_number)
time_mr = time.time() - start

print(f"Number: {test_number}")
print(f"Optimized method: {result} in {time_optimized*1000:.2f}ms")
print(f"Miller-Rabin: {result_mr} in {time_mr*1000:.2f}ms")
print(f"Speedup: {time_optimized/time_mr:.0f}x")

Generating Prime Numbers

def sieve_of_eratosthenes(limit):
    """
    Generate all primes up to limit
    Efficient algorithm: O(n log log n)
    """
    if limit < 2:
        return []
    
    # Create boolean array
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    
    # Sieve
    p = 2
    while p * p <= limit:
        if is_prime[p]:
            # Mark multiples of p as not prime
            for i in range(p * p, limit + 1, p):
                is_prime[i] = False
        p += 1
    
    # Collect primes
    return [num for num, prime in enumerate(is_prime) if prime]

# Generate first 100 primes
primes = sieve_of_eratosthenes(1000)
print(f"First 20 primes: {primes[:20]}")
print(f"Number of primes ≤ 1000: {len(primes)}")

# Generate large random prime
def generate_large_prime(bits=512):
    """Generate a large prime number (for cryptography)"""
    import secrets
    
    while True:
        # Generate random odd number
        candidate = secrets.randbits(bits)
        candidate |= (1 << bits - 1) | 1  # Set MSB and LSB
        
        # Test for primality
        if is_prime_miller_rabin(candidate, k=10):
            return candidate

# Example: generate 64-bit prime
large_prime = generate_large_prime(bits=64)
print(f"\nGenerated 64-bit prime: {large_prime}")
print(f"Is prime? {is_prime_miller_rabin(large_prime)}")

Greatest Common Divisor (GCD)

GCD is fundamental to cryptography and number theory.

def gcd_naive(a, b):
    """Naive GCD: check all divisors"""
    smaller = min(abs(a), abs(b))
    for i in range(smaller, 0, -1):
        if a % i == 0 and b % i == 0:
            return i
    return 1

def gcd_euclidean(a, b):
    """
    Euclidean algorithm: O(log min(a,b))
    Based on: gcd(a, b) = gcd(b, a mod b)
    """
    while b:
        a, b = b, a % b
    return abs(a)

def extended_gcd(a, b):
    """
    Extended Euclidean algorithm
    Returns gcd(a, b) and coefficients x, y such that:
    a*x + b*y = gcd(a, b)
    
    Used in RSA for finding modular inverses
    """
    if b == 0:
        return a, 1, 0
    
    gcd, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    
    return gcd, x, y

# Examples
a, b = 48, 18

print(f"gcd({a}, {b}) = {gcd_euclidean(a, b)}")

gcd, x, y = extended_gcd(a, b)
print(f"\nExtended GCD:")
print(f"gcd({a}, {b}) = {gcd}")
print(f"{a}*{x} + {b}*{y} = {a*x + b*y} = {gcd}")

Modular Multiplicative Inverse

Critical for decryption in RSA:

def mod_inverse(a, m):
    """
    Find modular multiplicative inverse of a modulo m
    Returns x such that (a * x) % m = 1
    
    Uses extended Euclidean algorithm
    """
    gcd, x, _ = extended_gcd(a, m)
    
    if gcd != 1:
        raise ValueError(f"Modular inverse doesn't exist (gcd({a}, {m}) = {gcd})")
    
    return x % m

# Example
a, m = 7, 26

inverse = mod_inverse(a, m)
print(f"Inverse of {a} mod {m} = {inverse}")
print(f"Verification: ({a} * {inverse}) mod {m} = {(a * inverse) % m}")

# Application: Solving linear congruence
# Solve: 7x ≡ 3 (mod 26)
# x = 3 * inverse(7, 26) mod 26

b = 3
x = (b * inverse) % m
print(f"\nSolve: 7x ≡ 3 (mod 26)")
print(f"x = {x}")
print(f"Verification: 7*{x} mod 26 = {(7*x) % m}")

RSA Encryption (Simplified)

Understanding the math behind RSA:

class RSA:
    """Simplified RSA implementation for educational purposes"""
    
    def __init__(self, bits=16):  # Small bits for demo
        """Generate RSA key pair"""
        # Generate two distinct primes
        self.p = generate_large_prime(bits // 2)
        self.q = generate_large_prime(bits // 2)
        
        while self.p == self.q:
            self.q = generate_large_prime(bits // 2)
        
        # Compute n = p * q
        self.n = self.p * self.q
        
        # Compute Euler's totient: φ(n) = (p-1)(q-1)
        phi_n = (self.p - 1) * (self.q - 1)
        
        # Choose public exponent e
        # Common choice: 65537 (2^16 + 1)
        self.e = 65537
        while gcd_euclidean(self.e, phi_n) != 1:
            self.e = generate_large_prime(bits // 4)
        
        # Compute private exponent d
        # d = e^(-1) mod φ(n)
        self.d = mod_inverse(self.e, phi_n)
        
        print(f"RSA Key Generation:")
        print(f"p = {self.p}")
        print(f"q = {self.q}")
        print(f"n = p*q = {self.n}")
        print(f"φ(n) = {phi_n}")
        print(f"Public key: (e={self.e}, n={self.n})")
        print(f"Private key: (d={self.d}, n={self.n})")
    
    def encrypt(self, message):
        """
        Encrypt message using public key
        ciphertext = message^e mod n
        """
        if message >= self.n:
            raise ValueError("Message too large for key size")
        
        ciphertext = pow(message, self.e, self.n)
        return ciphertext
    
    def decrypt(self, ciphertext):
        """
        Decrypt ciphertext using private key
        message = ciphertext^d mod n
        """
        message = pow(ciphertext, self.d, self.n)
        return message

# Example usage
print("\n" + "="*60)
rsa = RSA(bits=32)  # Small for demo

# Encrypt a message (must be < n)
message = 42
print(f"\nOriginal message: {message}")

ciphertext = rsa.encrypt(message)
print(f"Encrypted: {ciphertext}")

decrypted = rsa.decrypt(ciphertext)
print(f"Decrypted: {decrypted}")

print(f"\nSuccess! {message} == {decrypted}")

Hashing and Checksums

Using modular arithmetic for data integrity:

def simple_checksum(data):
    """
    Simple checksum using modular arithmetic
    Used in credit card numbers (Luhn algorithm), ISBN, etc.
    """
    if isinstance(data, str):
        data = [ord(c) for c in data]
    
    # Sum all values
    total = sum(data)
    
    # Return checksum (mod 256 for byte)
    return total % 256

def luhn_checksum(card_number):
    """
    Luhn algorithm (used for credit card validation)
    
    1. Double every second digit from right
    2. If doubled digit > 9, subtract 9
    3. Sum all digits
    4. If sum mod 10 = 0, valid
    """
    digits = [int(d) for d in str(card_number)]
    
    # Process from right to left
    checksum = 0
    for i, digit in enumerate(reversed(digits)):
        if i % 2 == 1:  # Every second digit
            digit *= 2
            if digit > 9:
                digit -= 9
        checksum += digit
    
    return checksum % 10 == 0

# Test credit card numbers
valid_card = "4532015112830366"
invalid_card = "4532015112830367"

print(f"\nLuhn algorithm:")
print(f"{valid_card}: {'Valid' if luhn_checksum(valid_card) else 'Invalid'}")
print(f"{invalid_card}: {'Valid' if luhn_checksum(invalid_card) else 'Invalid'}")

Chinese Remainder Theorem

Solving systems of modular equations:

def chinese_remainder_theorem(remainders, moduli):
    """
    Solve system of congruences:
    x ≡ a₁ (mod m₁)
    x ≡ a₂ (mod m₂)
    ...
    x ≡ aₙ (mod mₙ)
    
    where m₁, m₂, ..., mₙ are pairwise coprime
    """
    # Compute M = m₁ * m₂ * ... * mₙ
    M = 1
    for m in moduli:
        M *= m
    
    # Compute solution
    x = 0
    for a, m in zip(remainders, moduli):
        Mi = M // m
        yi = mod_inverse(Mi, m)
        x += a * Mi * yi
    
    return x % M

# Example: Find x such that:
# x ≡ 2 (mod 3)
# x ≡ 3 (mod 5)
# x ≡ 2 (mod 7)

remainders = [2, 3, 2]
moduli = [3, 5, 7]

x = chinese_remainder_theorem(remainders, moduli)
print(f"\nChinese Remainder Theorem:")
print(f"x ≡ 2 (mod 3)")
print(f"x ≡ 3 (mod 5)")
print(f"x ≡ 2 (mod 7)")
print(f"\nSolution: x = {x}")

# Verify
print(f"\nVerification:")
for a, m in zip(remainders, moduli):
    print(f"{x} mod {m} = {x % m} (expected: {a}) ✓" if x % m == a else "✗")

Real-World Application: Password Storage

import hashlib
import secrets

class PasswordHasher:
    """Secure password hashing using cryptographic principles"""
    
    @staticmethod
    def hash_password(password, salt=None):
        """
        Hash password with salt
        Uses SHA-256 (in practice, use bcrypt or argon2)
        """
        if salt is None:
            # Generate random salt
            salt = secrets.token_bytes(32)
        
        # Combine password and salt
        password_bytes = password.encode('utf-8')
        
        # Hash using SHA-256
        hasher = hashlib.sha256()
        hasher.update(salt)
        hasher.update(password_bytes)
        
        password_hash = hasher.digest()
        
        return salt, password_hash
    
    @staticmethod
    def verify_password(password, salt, expected_hash):
        """Verify password against stored hash"""
        _, computed_hash = PasswordHasher.hash_password(password, salt)
        return computed_hash == expected_hash

# Example usage
password = "MySecurePassword123!"

print("Password Hashing Example:")
print(f"Original password: {password}")

# Hash the password
salt, password_hash = PasswordHasher.hash_password(password)
print(f"Salt (hex): {salt.hex()[:32]}...")
print(f"Hash (hex): {password_hash.hex()}")

# Verify correct password
is_valid = PasswordHasher.verify_password(password, salt, password_hash)
print(f"\nVerify correct password: {is_valid} ✓")

# Verify wrong password
is_valid = PasswordHasher.verify_password("WrongPassword", salt, password_hash)
print(f"Verify wrong password: {is_valid} ✓")

Key Takeaways

• Modular arithmetic powers hash tables, cryptography, and cyclic operations

• Prime numbers are the foundation of modern encryption (RSA, Diffie-Hellman)

• GCD and modular inverses enable cryptographic operations

• Number theory isn't abstract—it secures every HTTPS connection

• Efficient algorithms (modular exponentiation, Miller-Rabin) make cryptography practical

• Understanding the math helps you use crypto libraries correctly and securely

What's Next

In the final article, we'll explore graph theory and algorithms—the mathematics behind networks, routing, dependencies, and social systems.

You'll learn:

• Graph representations and traversals

• Shortest path algorithms

• Network flow and optimization

• Real-world graph applications

Continue to Part 7: Graph Theory and Algorithms →

---

Navigation

• ← Part 5: Discrete Mathematics

• Back to Series Overview

• Part 7: Graph Theory and Algorithms →