Discrete Logarithm Calculator

Find x such that ax ≡ b (mod m). Essential for cryptography and number theory.

Discrete logarithm problem: Given a, b, m, find integer x such that ax mod m = b. This is the basis of many cryptographic systems.

Larger values increase search time.
5x ≡ 4 mod 23
2x ≡ 9 mod 13
3x ≡ 6 mod 17
2x ≡ 14 mod 19
7x ≡ 15 mod 31
2x ≡ 5 mod 11
Computing...

Understanding Discrete Logarithms

In modular arithmetic, the discrete logarithm is the inverse operation of modular exponentiation. Given ax ≡ b (mod m), finding x is the discrete logarithm problem (DLP).

Formal definition (group theory): Let G be a cyclic group of order n with generator g. For any element h ∈ G, the discrete logarithm logg(h) is the unique integer x (0 ≤ x < n) such that gx = h.

In our calculator, the group is usually the multiplicative group of integers modulo m (denoted (ℤ/mℤ)×) consisting of numbers coprime to m. If m is prime, this group is cyclic of order m‑1.

Existence and Uniqueness

  • Existence: For a solution to exist, b must be in the subgroup generated by a. If a and m are coprime, the powers of a cycle through a subset of residues modulo m. If b is not among them, no solution exists.
  • Uniqueness modulo the order: Let d = ordm(a) be the smallest positive integer such that ad ≡ 1 (mod m). If x is a solution, then x + kd are also solutions for any integer k. The calculator returns the smallest non‑negative x.
  • Primitive roots: If a is a primitive root modulo m (i.e., its order is φ(m)), then every b coprime to m appears as some power, and the discrete logarithm is unique modulo φ(m).

Example: 5x ≡ 4 (mod 23)

We compute powers of 5 mod 23:

x 5x mod 23
0 1
1 5
2 2
3 10
4 4
5 20
6 8
... ...

We see that x = 4 gives 4. Because 5 is a primitive root mod 23 (order 22), the full set of solutions is x ≡ 4 (mod 22).

Baby‑Step Giant‑Step Explained

For larger moduli, brute force (trying x = 0,1,2,…) is too slow. The baby‑step giant‑step algorithm finds x in O(√m) time using a meet‑in‑the‑middle approach:

  1. Let n = ⌈√m⌉.
  2. Compute and store “baby steps”: aj for j = 0,…,n (store j with the value).
  3. Compute a−n (the modular inverse of an).
  4. For i = 0,…,n, compute the “giant step”: b · (a−n)i mod m. If this value appears in the baby‑step table with exponent j, then x = i·n + j is a solution.

Example with a=5, b=4, m=23 (n = ⌈√23⌉ = 5):

Baby steps (j, aj mod 23): (0,1), (1,5), (2,2), (3,10), (4,4), (5,20)
an = 55 mod 23 = 20, inverse = 20−1 mod 23 = 15 (since 20·15=300≡1).
Giant steps i:
i=0: b·1 = 4 → found in baby steps at j=4 ⇒ x = 0·5+4 = 4.
So solution x=4.

Cryptographic Importance

The discrete logarithm problem is believed to be hard when the modulus is a large prime (e.g., 2048 bits). This hardness underpins many public‑key cryptosystems:

  • Diffie‑Hellman key exchange: Two parties agree on a secret key over an insecure channel without ever transmitting the key itself.
  • ElGamal encryption: A public‑key system based on DLP.
  • Digital Signature Algorithm (DSA): Used for digital signatures.
  • Elliptic curve cryptography (ECC): Uses groups of points on elliptic curves, where the DLP is even harder, allowing smaller key sizes.

For a 1024‑bit prime, solving a discrete logarithm with the best known algorithms (general number field sieve) is far beyond current computational capabilities. This is what makes these cryptosystems secure.

Computational limits: This calculator is for educational purposes. It uses algorithms that work for small moduli (up to about 106). For real cryptographic sizes, the numbers are astronomically larger and cannot be solved by any known method in reasonable time.

When No Solution Exists

If a and m are not coprime, a may not be invertible, and the sequence ax mod m eventually becomes periodic with a period that may not cover all residues. For example, 2x mod 4 yields only 0 and 2, so 2x ≡ 3 (mod 4) has no solution. The calculator will report “no solution” after exhausting the search range.

Frequently Asked Questions

If gcd(a,m) ≠ 1, then a is not invertible modulo m, and the equation ax ≡ b (mod m) may have no solution or multiple solutions. For example, 2x ≡ 3 (mod 4) has no solution because 2x mod 4 is always 0 or 2. The calculator will attempt to find a solution but may report none.

To prevent infinite loops and browser hangs, we limit the search to a user-defined maximum exponent. If the discrete logarithm is larger than that, you may need to increase the limit (but be aware that very large numbers will be slow).

Baby-step giant-step is a meet-in-the-middle algorithm that computes discrete logarithms in O(√m) time and space. It works by precomputing a table of "baby steps" (aj for j=0..√m) and then checking "giant steps" (b·a-i√m) to find a match. It's much faster than brute force for larger moduli.

If a and m are coprime, and the order of a modulo m is d, then if x is a solution, x + kd are also solutions for any integer k. The calculator returns the smallest non‑negative solution.

A primitive root modulo m is a number a such that its powers generate all numbers coprime to m. In other words, the order of a modulo m is φ(m). For prime m, primitive roots always exist.

For large numbers (e.g., 2000‑bit primes), no efficient classical algorithm is known. The best algorithms (index calculus, number field sieve) have subexponential but still impractical runtimes. This computational difficulty is the foundation of modern public‑key cryptography.