Number Theory is the branch of mathematics that studies the properties of integers and is fundamental to modern cryptography.

What is Number Theory?

Number theory provides the mathematical foundations for cryptography, especially in the study of prime numbers, congruences, and algebraic structures.

Fundamental Concepts

Prime Numbers

  • Definition: Natural number greater than 1 divisible only by 1 and itself
  • Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29…
  • Importance: Base of RSA cryptography
  • Distribution: Prime number theorem

Congruences

  • Definition: a ≡ b (mod n) if n divides (a - b)
  • Properties: Reflexive, symmetric, transitive
  • Operations: Addition, subtraction, multiplication
  • Application: Modular cryptography

Greatest Common Divisor (GCD)

  • Definition: Largest integer that divides both numbers
  • Euclidean Algorithm: Efficient calculation
  • Bézout’s Identity: ax + by = gcd(a,b)
  • Application: Key generation

Important Algorithms

Euclidean Algorithm

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def euclidean_gcd(a, b):
    """Calculate GCD using Euclidean algorithm"""
    while b != 0:
        a, b = b, a % b
    return a

def extended_euclidean(a, b):
    """Extended Euclidean algorithm"""
    if a == 0:
        return b, 0, 1
    
    gcd, x1, y1 = extended_euclidean(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    
    return gcd, x, y

# Example
gcd, x, y = extended_euclidean(48, 18)
print(f"GCD(48, 18) = {gcd}")
print(f"48*{x} + 18*{y} = {gcd}")

Modular Exponentiation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def modular_exponentiation(base, exponent, modulus):
    """Efficient modular exponentiation"""
    result = 1
    base = base % modulus
    
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus
        exponent = exponent >> 1
        base = (base * base) % modulus
    
    return result

# Example
result = modular_exponentiation(2, 10, 13)
print(f"2^10 mod 13 = {result}")

Primality Test

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

def is_prime(n):
    """Simple primality test"""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

def miller_rabin(n, k=40):
    """Miller-Rabin primality test"""
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    
    # Write n-1 as d * 2^r
    r = 0
    d = n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    
    # Test k times
    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

Important Theorems

Fermat’s Theorem

  • Statement: If p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p)
  • Application: Primality testing
  • Example: 2^6 ≡ 1 (mod 7)

Euler’s Theorem

  • Statement: If gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n)
  • φ Function: Euler’s function
  • Application: RSA cryptography
  • Example: 2^6 ≡ 1 (mod 9) because φ(9) = 6

Chinese Remainder Theorem

  • Statement: System of congruences with coprime moduli
  • Application: Calculation optimization
  • Example: Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)

Important Functions

Euler’s Function φ(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def euler_phi(n):
    """Calculate Euler's function φ(n)"""
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

# Example
phi_12 = euler_phi(12)
print(f"φ(12) = {phi_12}")

Möbius Function

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def mobius_function(n):
    """Calculate Möbius function μ(n)"""
    if n == 1:
        return 1
    
    count = 0
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            if n % (i * i) == 0:
                return 0
            count += 1
            n //= i
    
    if n > 1:
        count += 1
    
    return 1 if count % 2 == 0 else -1

Applications in Cryptography

RSA

  • Factorization: Difficulty of factoring large numbers
  • Euler’s Function: φ(n) = (p-1)(q-1)
  • Exponentiation: c = m^e mod n
  • Decryption: m = c^d mod n

Diffie-Hellman

  • Discrete Logarithm: Problem difficulty
  • Generators: Primitive elements
  • Exponentiation: g^a mod p
  • Exchange: Shared keys

Elliptic Curves

  • Groups: Group structure
  • Points: Points on curves
  • Operations: Point addition
  • Discrete Logarithm: ECDLP problem

Factorization Algorithms

Brute Force

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def brute_force_factorization(n):
    """Brute force factorization"""
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

Pollard’s Rho

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def pollard_rho(n):
    """Pollard's Rho algorithm"""
    if n % 2 == 0:
        return 2
    
    x = random.randint(1, n-1)
    y = x
    c = random.randint(1, n-1)
    d = 1
    
    while d == 1:
        x = (x*x + c) % n
        y = (y*y + c) % n
        y = (y*y + c) % n
        d = euclidean_gcd(abs(x - y), n)
    
    return d if d != n else None

Prime Number Generation

Random Generation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def generate_prime(bits):
    """Generate random prime number of 'bits' bits"""
    while True:
        # Generate random odd number
        n = random.getrandbits(bits)
        n |= (1 << bits - 1) | 1  # Ensure most significant bit
        
        if miller_rabin(n):
            return n

# Example
prime_1024 = generate_prime(1024)
print(f"1024-bit prime: {prime_1024}")

Sieve of Eratosthenes

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def sieve_of_eratosthenes(limit):
    """Sieve of Eratosthenes to find primes up to 'limit'"""
    primes = []
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, limit + 1, i):
                is_prime[j] = False
    
    for i in range(2, limit + 1):
        if is_prime[i]:
            primes.append(i)
    
    return primes

Computational Tools

SageMath

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# Example with SageMath
# Generate prime
p = random_prime(2^1024)

# Calculate GCD
gcd(48, 18)

# Modular exponentiation
power_mod(2, 10, 13)

# Primality test
is_prime(97)

# Euler's function
euler_phi(12)

SymPy

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from sympy import isprime, gcd, powermod, totient

# Primality test
isprime(97)

# GCD
gcd(48, 18)

# Modular exponentiation
powermod(2, 10, 13)

# Euler's function
totient(12)

References