Discrete Logarithm

This calculator works in the unit group, so the base must satisfy gcd(g, n) = 1. Difficulty depends on the factorization of n and of λ(n), and above all on the largest prime factor of ord_n(g). Computation runs locally in your browser.

The discrete logarithm lives in the cyclic subgroup ⟨g⟩; a solution of g^x ≡ h (mod n) exists exactly when h ∈ ⟨g⟩. Let r = ord_n(g). If g^x = g^y then g^(x−y) = 1, so r | x − y: the solution is unique modulo r, and the complete set is x ≡ x₀ (mod r) with 0 ≤ x₀ < r.

The order. The calculator factors n, computes λ(n), factors it, and reduces it to r as on the Multiplicative Order page. The prime factorization r = ∏ q_i^e_i is read off from that reduction, so nothing is factored again.

Quick obstruction. If h^r ≢ 1 (mod n) there is no solution, since (g^x)^r = 1. The converse fails for composite moduli: modulo 8, g=3 has order 2 and h=5 satisfies h² ≡ 1, yet 5\notin\{1,3\}. So the search always continues.

Pohlig-Hellman. An exponent modulo r is determined by its residues modulo each q_i^e_i. For one prime power write x_q = d₀ + d₁q + ⋯ + d_(e−1) q^(e−1) and let γ = g^(r/q), an element of order q. If the first k digits are known, then x − x_q is divisible by q^{k}, and raising h·g^(−x_q) to the power r/q^(k+1) kills all higher digits:

Each digit is a discrete logarithm in a group of prime order q; then x_q ← x_q + d_k q^k. The residues x ≡ x_i (mod q_i^e_i) are combined with the Chinese Remainder Theorem.

Baby-step giant-step. For a prime q let m = ⌈√q⌉ and write d = im + j. Then γ^d = c becomes c·γ^(−im) = γ^j: the baby steps store γ^j for 0\le j<m, and the giant steps look up c·γ^(−im). Work and memory are about √q. When √q entries do not fit in the memory budget (500,000 entries at most), the table stays at that size m and up to ⌈q/m⌉ giant steps are taken instead: the same memory, more time (up to 200,000,000 giant steps, which reaches q ≈ 10¹⁴). The table depends only on γ, so it is built once per prime and reused for every digit and every target h. Small primes (q\le 2048) use a full lookup table, and a small order (r\le 2000) is solved by walking 1,g,g^{2},\dots directly.

Difficulty. The cost is governed by the largest prime factor of r, not by its size: a huge order built from small prime powers is easy, while a much smaller order with one large prime factor can exceed the browser's memory and work limits. In that case the calculator says so and never reports "no solution".

Verification. Every result is checked: g^(x₀) ≡ h (mod n). If some prime factor is only a probable prime, a found exponent is still a verified solution; that the solution class is exactly x ≡ x₀ (mod r) assumes the probable-prime factorization is correct.

Related: Multiplicative Order · Primitive Roots · Modular Exponentiation · Modular Inverse · Chinese Remainder Theorem · Prime Factorization