number-theory

# Number Theory ## What I do I provide comprehensive expertise in number theory, the branch of mathematics concerned with the properties and relationships of integers. I enable you to work with divisibility, prime numbers, modular arithmetic, Diophantine equations, and number-theoretic algorithms. My knowledge spans from fundamental theorems (fundamental theorem of arithmetic, Fermat's little theorem) to cryptographic applications (RSA, elliptic curves) essential for cryptography, computer security, algorithm design, and pure mathematics research. ## When to use me Use number theory when you need to: implement cryptographic algorithms (RSA, ECC, Diffie-Hellman), generate and test prime numbers for key generation, solve modular equations and congruences, implement hash functions and checksums, optimize algorithms using number-theoretic transforms, analyze integer partitions and Diophantine equations, validate digital signatures, or apply Chinese Remainder Theorem for system of congruences. ## Core Concepts - **Divisibility and GCD**: Relationships between integers where a|b means a divides b, with greatest common divisor computation. - **Prime Numbers and Primality Testing**: Numbers greater than 1 with no positive divisors, essential for cryptography. - **Modular Arithmetic**: Arithmetic on remainders with operations modulo m, fundamental to modern cryptography. - **Euler's Theorem and Totient Function**: Generalization of Fermat's little theorem with φ(n) counting coprime residues. - **Chinese Remainder Theorem**: System of congruences with pairwise coprime moduli has a unique solution modulo product. - **Quadratic Residues**: Numbers that are squares modulo p, used in cryptographic protocols. - **Primitive Roots and Discrete Logarithms**: Generators of multiplicative groups and their computational hardness. - **Diophantine Equations**: Polynomial equations seeking integer solutions, including linear and exponential forms. - **Modular Inverses**: Numbers satisfying ax ≡ 1 (mod m), existing iff gcd(a,m)=1. - **Continued Fractions**: Expressions representing numbers through sequences of integers, useful in approximation. ## Code Examples ### Divisibility and GCD Algorithms ```python import math def extended_gcd(a, b): """ Extended Euclidean Algorithm. Returns (g, x, y) such that ax + by = g = gcd(a, b) """ if b == 0: return (abs(a), 1 if a > 0 else -1, 0) g, x1, y1 = extended_gcd(b, a % b) x = y1 y = x1 - (a // b) * y1 return (g, x, y) def gcd(a, b): """Compute greatest common divisor using Euclidean algorithm.""" a, b = abs(a), abs(b) while b: a, b = b, a % b return a def lcm(a, b): """Compute least common multiple.""" if a == 0 or b == 0: return 0 return abs(a * b) // gcd(a, b) def bezout_coefficients(a, b): """Find x, y such that ax + by = gcd(a, b).""" g, x, y = extended_gcd(a, b) return x, y # Examples print(f"gcd(48, 18) = {gcd(48, 18)}") print(f"lcm(12, 15) = {lcm(12, 15)}") x, y = bezout_coefficients(48, 18) print(f"Bézout coefficients for 48, 18: x={x}, y={y}") print(f"Verification: 48*({x}) + 18*({y}) = {48*x + 18*y}") # Check if ax + by = c has integer solutions def has_diophantine_solution(a, b, c): """Check if ax + by = c has integer solutions.""" return c % gcd(a, b) == 0 print(f"\n24x + 18y = 6 has solution: {has_diophantine_solution(24, 18, 6)}") print(f"24x + 18y = 7 has solution: {has_diophantine_solution(24, 18, 7)}") # Find particular solution def solve_linear_diophantine(a, b, c): """Find particular solution to ax + by = c.""" g, x0, y0 = extended_gcd(a, b) if c % g != 0: return None # No solution scale = c // g return (x0 * scale, y0 * scale) solution = solve_linear_diophantine(24, 18, 6) print(f"Particular solution to 24x + 18y = 6: {solution}") ``` ### Modular Arithmetic ```python def mod_pow(base, exponent, modulus): """Modular exponentiation using binary exponentiation.""" result = 1 base = base % modulus while exponent > 0: if exponent % 2 == 1: result = (result * base) % modulus exponent //= 2 base = (base * base) % modulus return result def mod_inverse(a, modulus): """Find modular inverse using extended Euclidean algorithm.""" g, x, y = extended_gcd(a, modulus) if g != 1: return None # Inverse doesn't exist return x % modulus def chinese_remainder_theorem(congruences): """ Solve system of congruences: x ≡ a1 (mod n1) x ≡ a2 (mod n2) ... where moduli are pairwise coprime. """ # Find M = product of all moduli moduli = [n for _, n in congruences] M = 1 for n in moduli: M *= n result = 0 for a, n in congruences: Mi = M // n # Find inverse of Mi modulo n _, y, _ = extended_gcd(Mi, n) result += a * Mi * y return result % M # Examples print(f"3^17 mod 1000 = {mod_pow(3, 17, 1000)}") print(f"Inverse of 17 mod 100: {mod_inverse(17, 100)}") # Chinese Remainder Theorem example congruences = [(2, 3), (3, 5), (2, 7)] solution = chinese_remainder_theorem(congruences) print(f"\nCRT solution for x≡2(3), x≡3(5), x≡2(7): x = {solution}") print(f"Verification: {solution} mod 3 = {solution % 3}, mod 5 = {solution % 5}, mod 7 = {solution % 7}") # Solve using Garner's algorithm (efficient for CRT) def garner_algorithm(congruences, mod=None): """Garner's algorithm for CRT (handles non-coprime with consistency check).""" x = 0 M = 1 for a, n in congruences: # Find t such that x + M*t ≡ a (mod n) t = mod_inverse(M % n, n) * ((a - x) % n) t %= n x += M * t M *= n return x x_garner = garner_algorithm(congruences) print(f"Garner: x = {x_garner}") ``` ### Primality Testing ```python import random import math def is_probable_prime(n, k=10): """Miller-Rabin primality test (probabilistic).""" if n < 2: return False if n in (2, 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 # Test k rounds 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 = (x * x) % n if x == n - 1: break else: return False return True def deterministic_primality_test(n): """Deterministic primality test for n < 2^64.""" if n < 2: return False if n in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37): return True if n % 2 == 0: return False # Miller-Rabin with deterministic bases for 64-bit integers bases = [2, 325, 9375, 28178, 450775, 9780504, 1795265022] r, d = 0, n - 1 while d % 2 == 0: r += 1 d //= 2 for a in bases: if a % n == 0: continue x = pow(a, d, n) if x == 1 or x == n - 1: continue for _ in range(r - 1): x = (x * x) % n if x == n - 1: break else: return False return True def sieve_of_eratosthenes(limit): """Generate all primes up to limit.""" if limit < 2: return [] sieve = [True] * (limit + 1) sieve[0] = sieve[1] = False for p in range(2, int(limit ** 0.5) + 1): if sieve[p]: for multiple in range(p * p, limit + 1, p): sieve[multiple] = False return [i for i, is_prime in enumerate(sieve) if is_prime] # Examples primes = sieve_of_eratosthenes(100) print(f"Primes up to 100: {primes}") print(f"Number of primes: {len(primes)}") # Test primality test_numbers = [101, 1000003, 2**127 - 1] # 2^127 - 1 is a Mersenne prime for n in test_numbers: print(f"{n} is prime: {deterministic_primality_test(n)}") # RSA-style primality test large_prime_candidate = 2305843009213693951 # 2^61 - 1 print(f"\n{2**61 - 1} is prime: {deterministic_primality_test(large_prime_candidate)}") ``` ### Cryptographic Applications ```python import random def generate_rsa_keys(bit_length=2048): """Generate RSA key pair.""" # Find two large primes def find_prime(bits): while True: n = random.getrandbits(bits) if deterministic_primality_test(n): if deterministic_primality_test((n - 1) // 2): return n p = find_prime(bit_length // 2) q = find_prime(bit_length // 2) while q == p: q = find_prime(bit_length // 2) n = p * q phi = (p - 1) * (q - 1) # Choose e (commonly 65537) e = 65537 while math.gcd(e, phi) != 1: e = random.randrange(3, phi, 2) # Compute d as modular inverse of e d = mod_inverse(e, phi) return (e, n), (d, n) # Public key, private key def rsa_encrypt(message, public_key): """Encrypt message using RSA.""" e, n = public_key return pow(message, e, n) def rsa_decrypt(ciphertext, private_key): """Decrypt message using RSA.""" d, n = private_key return pow(ciphertext, d, n) # RSA example (small numbers for demonstration) def rsa_demo(): # Generate keys with smaller primes for demo p, q = 61, 53 n = p * q phi = (p - 1) * (q - 1) e = 17 # Public exponent d = mod_inverse(e, phi) # Private exponent public_key = (e, n) private_key = (d, n) message = 42 ciphertext = rsa_encrypt(message, public_key) decrypted = rsa_decrypt(ciphertext, private_key) print(f"\nRSA Demo:") print(f" p = {p}, q = {q}, n = {n}") print(f" e = {e}, d = {d}") print(f" Message: {message}") print(f" Ciphertext: {ciphertext}") print(f" Decrypted: {decrypted}") print(f" Success: {message == decrypted}") rsa_demo() # Diffie-Hellman key exchange def diffie_hellman(p, g, private_a, private_b): """Demonstrate Diffie-Hellman key exchange.""" # Public parameters: prime p and generator g # Alice computes A = g^a mod p A = pow(g, private_a, p) # Bob computes B = g^b mod p B = pow(g, private_b, p) # Alice computes shared secret: B^a mod p shared_alice = pow(B, private_a, p) # Bob computes shared secret: A^b mod p shared_bob = pow(A, private_b, p) return shared_alice, shared_bob # DH example p = 23 # Small prime for demo g = 5 # Generator alice_private = 4 bob_private = 3 shared_a, shared_b = diffie_hellman(p, g, alice_private, bob_private) print(f"\nDiffie-Hellman:") print(f" Prime p = {p}, Generator g = {g}") print(f" Alice's private: {alice_private}, Bob's private: {bob_private}") print(f" Shared secret: {shared_a} (both parties agree)") ``` ### Number-Theoretic Functions ```python import math def euler_totient(n): """Compute Euler's totient 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 def mobius_function(n): """Compute Möbius function μ(n).""" if n == 1: return 1 prime_factors = set() p = 2 while p * p <= n: if n % p == 0: if p in prime_factors: # Squared prime factor return 0 prime_factors.add(p) while n % p == 0: n //= p p += 1 if n > 1: prime_factors.add(n) return -1 if len(prime_factors) % 2 == 1 else 1 def divisor_function(n, k=1): """Compute σ_k(n) = sum of k-th powers of divisors.""" total = 0 p = 2 while p * p <= n: if n % p == 0: exp = 0 while n % p == 0: n //= p exp += 1