Fotools
EN

Congruence Equation Solver

Input Parameters

Quick Example:

Calculation Result

Enter parameters and click "Solve Equation"

Algorithm Explanation:

1. Linear Congruence Equation ax ≡ b (mod m):
  • Existence of Solutions:The equation has a solution if and only if gcd(a, m) divides b (i.e., b is divisible by gcd(a, m))
  • Number of Solutions:If solutions exist, there are d = gcd(a, m) distinct solutions modulo m
  • Solution Method:
    1. Calculate d = gcd(a, m)
    2. Check if d divides b; if not, there is no solution
    3. Divide both sides of the equation by d: (a/d)x ≡ (b/d) (mod m/d)
    4. Use the Extended Euclidean Algorithm to find the inverse of a/d modulo m/d'
    5. Calculate x₀ = a' × (b/d) mod (m/d)
    6. General solution: x = x₀ + k(m/d), where k = 0, 1, ..., d-1
2. Exponential congruence equation a^x ≡ b (mod m) (Discrete Logarithm Problem):
  • Problem description:Given a, b, m, find the smallest non-negative integer x such that a^x ≡ b (mod m)
  • Existence of Solutions:
    • If gcd(a, m) = 1 and b is an element of the cyclic group generated by a modulo m, then a solution exists
    • Verification method: enumerate powers of a until b is found or a full cycle is completed
  • Solution Method:
    • Brute force search in a small range:Enumerate x = 0, 1, 2, ... until a solution is found or the search limit is reached
    • Baby-step Giant-step algorithm:Time complexity O(√m), suitable for medium-sized problems
    • Pollard's rho algorithm:Applicable for large prime moduli
  • Periodicity:If x₀ is a solution, then x = x₀ + kφ(m) is also a solution (where φ(m) is Euler's totient function)
3. Application scenarios:
  • Cryptography:RSA, Diffie-Hellman key exchange, ElGamal encryption
  • Number theory research:Primitive Roots, Quadratic Residues, Chinese Remainder Theorem
  • Random Number Generation:Linear Congruential Generator (LCG)
  • Hash Functions:Application of Modular Arithmetic in Hash Tables
  • Competitive Programming:Fast Exponentiation, Modular Inverse, Number Theory Problems

Algorithm Complexity:

  • Linear Congruence Equations:O(log m) (Complexity of Extended Euclidean Algorithm)
  • Exponential Congruence Equations (Brute Force):O(n), where n is the search limit
  • Exponential Congruence Equations (BSGS):O(√m), requires extra space

Important Theorems:

  • Bézout's Theorem:The equation ax + my = gcd(a, m) always has integer solutions
  • Fermat's Little Theorem:If p is prime and gcd(a, p) = 1, then a^(p-1) ≡ 1 (mod p)
  • Euler's Theorem:If gcd(a, m) = 1, then a^φ(m) ≡ 1 (mod m)
  • Chinese Remainder Theorem:Can solve systems of congruences