Introduction
Given a generator g, a target h, and a prime modulus p, the discrete logarithm problem asks: find x such that g^x = h (mod p). This is easy to compute in one direction (exponentiation) but believed hard to reverse, and that asymmetry is the foundation of Diffie-Hellman, ElGamal, and DSA. This calculator solves the problem by brute force, trying x = 0, 1, 2, 3, ... until g^x equals h mod p. It works only for small groups, but that is exactly the point: it shows you why the problem is hard and how quickly the search space explodes. Paste your values and watch the search run.
What this tool does
- Solve g^x = h (mod p) by brute force, trying x = 0, 1, 2, ... until a match is found or the group order is reached
- Display each trial as a row showing x, g^x mod p, and whether it equals h, so you can see the search progress step by step
- Report the solution x (the discrete logarithm) along with the number of trials it took to find it
- Detect when no solution exists (h is not in the subgroup generated by g) and report the group order of g
- Handle BigInt inputs, so you can test with large primes even though the brute-force search will be slow for them
- Run entirely in your browser with no server communication
How this tool works
The tool takes three inputs: a generator g, a target h, and a modulus p. It computes successive powers of g modulo p, starting from g^0 = 1, then g^1, g^2, g^3, and so on. At each step it compares the result to h. If they match, it reports x as the discrete logarithm and stops. If it reaches x equal to the order of g (the smallest positive k such that g^k = 1 mod p) without finding h, it reports that h is not in the subgroup generated by g and no solution exists.
The search uses iterative multiplication: instead of computing g^x from scratch each time (which would be O(x log x) with fast exponentiation), it multiplies the previous result by g mod p, so each step is a single modular multiplication. This makes the brute-force search O(x) in time and O(1) in space.
The trace panel shows a table of trials. For example, with g = 3, h = 13, p = 17: x = 0 gives 1, x = 1 gives 3, x = 2 gives 9, x = 3 gives 27 mod 17 = 10, x = 4 gives 30 mod 17 = 13. Match found at x = 4. The tool shows all five rows so you can see how the powers cycle through the group.
For large p, the tool limits the number of trials displayed (showing the first and last few) but continues searching in the background. If the group order is large (say p is a 2048-bit prime), the brute-force search will not finish in any reasonable time, which is precisely the security assumption behind Diffie-Hellman. The tool makes this concrete: you can watch it crawl through values and realize that a 2048-bit group makes brute force hopeless.
How the discrete logarithm problem works
The discrete logarithm problem (DLP) is: given g, h, and p, find x such that g^x = h (mod p). Computing g^x mod p is easy with square-and-multiply in O(log x) multiplications. Reversing it, finding x from g and h, is believed hard. This asymmetry is the basis of discrete-log-based cryptography.
Diffie-Hellman key exchange (RFC 7919) relies on DLP difficulty. Alice picks a, sends g^a mod p. Bob picks b, sends g^b mod p. Both compute g^(ab) mod p. An attacker sees g^a and g^b but cannot compute g^(ab) without solving the DLP.
ElGamal encryption and DSA (Digital Signature Algorithm, FIPS 186-5) similarly depend on DLP hardness in prime-order subgroups.
The best known algorithm for DLP in a prime field Z/pZ is the number field sieve (NFS), which runs in sub-exponential time: L_p[1/3, c] = exp(c * (ln p)^(1/3) * (ln ln p)^(2/3)). This is not polynomial, but much faster than brute force. For a 2048-bit prime, NFS is considered infeasible today, which is why NIST SP 800-56A recommends 2048-bit groups for security through 2030.
For elliptic curve groups, the best known algorithm is generic: Pollard's rho, running in O(sqrt(n)) where n is the group order. There is no known sub-exponential algorithm for well-chosen elliptic curves. This is why a 256-bit elliptic curve group (like P-256) provides security comparable to a 3072-bit finite field group, as noted in NIST SP 800-57.
For small groups, brute force works fine. The Baby-Step Giant-Step algorithm (Shanks, 1971) solves DLP in O(sqrt(n)) time and space, and Pollard's rho does it in O(sqrt(n)) time and O(1) space. These are the practical algorithms for medium-sized groups. See the Baby-Step Giant-Step Demo for a visualization of the O(sqrt(n)) approach.
How to use this tool
- Enter the generator g (an integer whose powers generate a subgroup of Z/pZ)
- Enter the target h (the value whose logarithm you want to find)
- Enter the modulus p (typically a prime, so that Z/pZ is a field and g has a well-defined multiplicative order)
- Click Solve. The tool starts computing g^0, g^1, g^2, ... mod p and comparing each to h
- Watch the trace table fill in: each row shows x, g^x mod p, and whether it matches h
- If a match is found, the tool reports x as the discrete logarithm and the number of trials. If the search reaches the group order without a match, it reports that no solution exists
- For large p, note how quickly the search becomes impractical, which is the security basis of Diffie-Hellman
Real-world examples
Solving a small DLP
Input: g = 5, h = 3, p = 23. The tool computes: 5^0 = 1, 5^1 = 5, 5^2 = 2, 5^3 = 10, 5^4 = 4, 5^5 = 20, 5^6 = 8, 5^7 = 17, 5^8 = 16, 5^9 = 11, 5^10 = 9, 5^11 = 22, 5^12 = 18, 5^13 = 21, 5^14 = 13, 5^15 = 19, 5^16 = 3. Match found at x = 16. So log_5(3) mod 23 = 16. The search took 17 trials.
No solution exists
Input: g = 4, h = 3, p = 7. The powers of 4 mod 7 are: 4^0 = 1, 4^1 = 4, 4^2 = 2, 4^3 = 1. The subgroup generated by 4 is {1, 2, 4}, which has order 3. Since 3 is not in this subgroup, no solution exists. The tool reports this after 3 trials.
Why large primes are safe
Input: g = 2, h = some value, p = a 256-bit prime. The group order is about 2^256. Brute force would need up to 2^256 trials, which is about 10^77. At a billion trials per second, that would take 10^68 seconds, far longer than the age of the universe. This is why Diffie-Hellman with a 2048-bit prime is considered secure.
Comparison with similar methods
| Method | Complexity | Typical use |
|---|---|---|
| Brute force | O(n) time, O(1) space | Small groups only, this tool |
| Baby-Step Giant-Step (Shanks 1971) | O(sqrt(n)) time and space | Medium groups, see BSGS Demo |
| Pollard's rho | O(sqrt(n)) time, O(1) space | Medium to large groups, practical |
| Pohlig-Hellman | O(sqrt(p_max)) for smooth order | Groups with smooth order (insecure) |
| Number field sieve | L_p[1/3, c] sub-exponential | Prime fields, best known for Z/pZ |
| Pollard's rho for EC | O(sqrt(n)) for elliptic curves | Best known for EC groups, no sub-exponential algorithm |
Limitations or considerations
This tool uses brute force, which is O(n) where n is the group order. For a prime p, the group order can be up to p-1. For p with 20 digits, the search may take millions of trials and several seconds. For p with 40 digits, it will not finish in any reasonable time. For p with 200+ digits (as used in real cryptography), brute force is hopeless, which is the entire point.
For groups larger than about 10^12, use the Baby-Step Giant-Step Demo, which runs in O(sqrt(n)) time. For even larger groups, you would need Pollard's rho or the number field sieve, neither of which this tool implements.
The tool assumes p is prime. If p is composite, the multiplicative group Z/pZ is not a field, and the structure is more complex (it depends on the factorization of p). The tool does not check primality of p; if you need that, use the Miller-Rabin Primality Test.
The tool does not handle elliptic curve discrete logarithms. The ECDLP (g^x = h on an elliptic curve) is a different problem with different algorithms. See the Elliptic Curve Calculator for EC operations.
Frequently asked questions
Why is the discrete logarithm problem hard?
Because exponentiation modulo p is a one-way function: computing g^x mod p is easy (O(log x) with square-and-multiply), but no known polynomial-time algorithm reverses it for large p. The best known algorithm for prime fields (the number field sieve) is sub-exponential, and for elliptic curves the best known is O(sqrt(n)). This asymmetry is what makes Diffie-Hellman and DSA secure.
What is the difference between this and Baby-Step Giant-Step?
This tool uses brute force, trying x = 0, 1, 2, ... one at a time, which is O(n) in time. Baby-Step Giant-Step (Shanks 1971) uses a meet-in-the-middle approach that runs in O(sqrt(n)) time and space. For a group of order 10^12, brute force needs 10^12 trials while BSGS needs about 10^6. See the BSGS Demo.
What happens if h is not in the subgroup generated by g?
The tool searches until it reaches the order of g (the smallest k where g^k = 1 mod p) and then reports that no solution exists. For example, if g = 4 mod 7, the subgroup is {1, 2, 4} with order 3, so h = 3 has no solution. This happens when h is not a power of g.
How does this relate to Diffie-Hellman?
Diffie-Hellman security depends on the Computational Diffie-Hellman (CDH) problem: given g^a and g^b, compute g^(ab) mod p. If you could solve the discrete logarithm problem, you could solve CDH (extract a from g^a, then compute (g^b)^a). So DLP hardness implies DH security. See the Diffie-Hellman Key Exchange tool.
Can this tool break real Diffie-Hellman?
No. Real DH uses 2048-bit or larger primes, where the group order is about 2^2048. Brute force would need up to 2^2048 trials, which is physically impossible. Even the number field sieve, the best known algorithm, is infeasible for well-chosen 2048-bit groups. This tool is for understanding the problem, not breaking real crypto.
Conclusion
The discrete logarithm problem is one of the two pillars of public-key cryptography (the other being integer factorization for RSA). This brute-force calculator makes the problem tangible: you can see the search crawl through values and feel why a 2048-bit group makes it hopeless. For a faster algorithm that handles larger groups, try the Baby-Step Giant-Step Demo. To see where DLP hardness is used in practice, experiment with the Diffie-Hellman Key Exchange tool. To test whether your modulus p is actually prime (which is required for the group structure to be correct), use the Miller-Rabin Primality Test.