number-theory

name	number-theory
description	Number theory fundamentals including divisibility, prime numbers, modular arithmetic, Diophantine equations, and cryptographic applications.
category	mathematics
tags	["mathematics","number-theory","primes","modular-arithmetic","cryptography","diophantine","algorithms"]
difficulty	intermediate
author	neuralblitz

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

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) = ")

x, y = bezout_coefficients(, )
()
()


 ():
    
     c % gcd(a, b) == 

()
()


 ():
    
    g, x0, y0 = extended_gcd(a, b)
    
     c % g != :
           
    
    scale = c // g
     (x0 * scale, y0 * scale)

solution = solve_linear_diophantine(, , )
()

Modular Arithmetic

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, )}")
()


congruences = [(, ), (, ), (, )]
solution = chinese_remainder_theorem(congruences)
()
()


 ():
    
    x = 
    M = 
    
     a, n  congruences:
        
        t = mod_inverse(M % n, n) * ((a - x) % n)
        t %= n
        x += M * t
        M *= n
    
     x

x_garner = garner_algorithm(congruences)
()

Primality Testing

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
    
     

 ():
    
     n < :
         
     n  (, , , , , , , , , , , ):
         
     n %  == :
         
    
    
    bases = [, , , , , , ]
    
    r, d = , n - 
     d %  == :
        r += 
        d //= 
    
     a  bases:
         a % n == :
            
        x = (a, d, n)
         x ==   x == n - :
            
         _  (r - ):
            x = (x * x) % n
             x == n - :
                
        :
             
    
     

 ():
    
     limit < :
         []
    
    sieve = [] * (limit + )
    sieve[] = sieve[] = 
    
     p  (, (limit ** ) + ):
         sieve[p]:
             multiple  (p * p, limit + , p):
                sieve[multiple] = 
    
     [i  i, is_prime  (sieve)  is_prime]


primes = sieve_of_eratosthenes()
()
()


test_numbers = [, , ** - ]  
 n  test_numbers:
    ()


large_prime_candidate =   
()

Cryptographic Applications

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)


 ():
    
    p, q = , 
    n = p * q
    phi = (p - ) * (q - )
    
    e =   
    d = mod_inverse(e, phi)  
    
    public_key = (e, n)
    private_key = (d, n)
    
    message = 
    ciphertext = rsa_encrypt(message, public_key)
    decrypted = rsa_decrypt(ciphertext, private_key)
    
    ()
    ()
    ()
    ()
    ()
    ()
    ()

rsa_demo()


 ():
    
    
    
    
    A = (g, private_a, p)
    
    
    B = (g, private_b, p)
    
    
    shared_alice = (B, private_a, p)
    
    
    shared_bob = (A, private_b, p)
    
     shared_alice, shared_bob


p =   
g =    
alice_private = 
bob_private = 

shared_a, shared_b = diffie_hellman(p, g, alice_private, bob_private)
()
()
()
()

Number-Theoretic Functions

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=):
    
    total = 
    p = 
    
     p * p <= n:
         n % p == :
            exp = 
             n % p == :
                n //= p
                exp += 
            total += (p**(k * (exp + )) - ) // (p**k - )  p**k !=   (exp + )
        p += 
    
     n > :
        total += n**k
    
     total

 ():
    
    factors = {}
    p = 
    
     p * p <= n:
         n % p == :
            factors[p] = factors.get(p, ) + 
            n //= p
        p += 
    
     n > :
        factors[n] = factors.get(n, ) + 
    
     factors


()
()
()
()
()


 n  [, , ]:
    phi_n = euler_totient(n)
    phi_factors = [euler_totient(p)  p  prime_factorization(n)]
    phi_product = math.prod(phi_factors)
    ()


 ():
    
    factors = prime_factorization(n)
    
     n == :
         
    
     n ==   n == :
         n // 
    
     n %  ==   n > :
        factors[] -= 
    
    lcm_val = 
     p, exp  factors.items():
         p ==   exp > :
            lcm_val = (lcm_val, **(exp - ))
        :
            lcm_val = (lcm_val, (p - ) * p**(exp - ))
    
     lcm_val

()  

Best Practices

• Use deterministic primality tests (Miller-Rabin with specific bases) for cryptographic applications rather than probabilistic versions.
• Always reduce intermediate results modulo n in modular arithmetic to prevent integer overflow.
• When computing modular inverses, verify that the modulus and base are coprime first.
• For RSA key generation, ensure primes p and q are sufficiently far apart to prevent Fermat factorization attacks.
• Use Chinese Remainder Theorem in RSA decryption for approximately 4x speedup.
• Implement secure random number generation for cryptographic key generation; Mersenne Twister is NOT cryptographically secure.
• Consider timing attacks on modular exponentiation; use constant-time algorithms in production systems.
• When implementing number-theoretic algorithms, handle edge cases (n=0, n=1, negative numbers) explicitly.
• Use Montgomery reduction for efficient modular multiplication in cryptographic implementations.
• Validate inputs to cryptographic functions to prevent side-channel attacks and edge case vulnerabilities.