Editing Number Theory (section)

== <span style="color: #FFFFFF;">Applying</span> ==
'''Number theory in cryptographic applications:'''
<syntaxhighlight lang="python">
import math
import random
from functools import reduce

# === Core Number Theory ===

def gcd(a: int, b: int) -> int:
    """Euclidean algorithm — O(log min(a,b))."""
    while b:
        a, b = b, a % b
    return a

def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    """Extended Euclidean: returns (gcd, x, y) where ax + by = gcd(a,b)."""
    if a == 0:
        return b, 0, 1
    g, x, y = extended_gcd(b % a, a)
    return g, y - (b // a) * x, x

def mod_inverse(a: int, n: int) -> int:
    """Modular inverse of a mod n (requires gcd(a,n) = 1)."""
    g, x, _ = extended_gcd(a % n, n)
    if g != 1:
        raise ValueError(f"Inverse doesn't exist: gcd({a},{n}) = {g}")
    return x % n

def power_mod(base: int, exp: int, mod: int) -> int:
    """Fast modular exponentiation: base^exp mod mod — O(log exp)."""
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

def euler_totient(n: int) -> int:
    """Euler's totient φ(n) — count of integers coprime to n in [1,n]."""
    result = n
    p = 2
    temp = n
    while p * p <= temp:
        if temp % p == 0:
            while temp % p == 0:
                temp //= p
            result -= result // p
        p += 1
    if temp > 1:
        result -= result // temp
    return result

# === Primality Testing ===
def miller_rabin(n: int, k: int = 10) -> bool:
    """Probabilistic primality test. Returns True if n is probably prime."""
    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
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = power_mod(a, d, n)
        if x == 1 or x == n - 1: continue
        for _ in range(r - 1):
            x = power_mod(x, 2, n)
            if x == n - 1: break
        else:
            return False
    return True  # Probably prime (error probability < 4^{-k})

# === RSA Key Generation (educational) ===
def generate_rsa_keys(bits: int = 512):
    """Generate RSA public/private key pair."""
    # In practice, use cryptography library. This is for education only.
    from sympy import randprime  # For proper prime generation
    p = randprime(2_'(bits//2-1), 2_'(bits//2))
    q = randprime(2_'(bits//2-1), 2_'(bits//2))
    n = p * q          # Public modulus
    phi = (p-1)*(q-1)  # Euler's totient
    e = 65537          # Standard public exponent
    d = mod_inverse(e, phi)  # Private exponent: ed ≡ 1 (mod φ(n))
    return (n, e), (n, d)    # (public_key, private_key)

public_key, private_key = generate_rsa_keys(512)
n, e = public_key
# Encrypt: ciphertext = message^e mod n
message = 42
ciphertext = power_mod(message, e, n)
# Decrypt: plaintext = ciphertext^d mod n
decrypted = power_mod(ciphertext, private_key[1], n)
print(f"Original: {message} → Encrypted → Decrypted: {decrypted}")
assert message == decrypted
</syntaxhighlight>

; Key results and open problems
: '''Proved''' → Infinitely many primes (Euclid) · Prime Number Theorem (1896) · Fermat's Last Theorem (Wiles, 1995) · 4-Color Theorem (1976) · Poincaré Conjecture (Perelman, 2003)
: '''Open''' → Riemann Hypothesis · Goldbach's Conjecture · Twin Prime Conjecture · abc Conjecture · P vs NP (related to integer factoring)
</div>

<div style="background-color: #8B4500; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">