Discrete logarithm solver
Ask which power of 2 leaves 5 modulo 13 and you get 9, because 2^9 ≡ 5 (mod 13). Enter a base, a target and a prime modulus to find the smallest exponent, with an equation you can check. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- G
- 2
- H
- 5
- Power (W)
- 13
- X
- 9
- Equation
- 2^9 ≡ 5 (mod 13)
The discrete logarithm problem asks for an integer x such that a given base g raised to x is congruent to a target h modulo a prime p. It underpins Diffie–Hellman key exchange, ElGamal encryption, and many textbook exercises in algebraic cryptography. This capacity implements the classical baby-step giant-step algorithm: a deterministic, square-root-time search that either recovers the smallest non-negative exponent or proves that h is not a power of g in the multiplicative group modulo p.
What the discrete logarithm asks for
Given integers g, h, and a prime p, the discrete logarithm of h to base g modulo p is any integer x satisfying g to the power x congruent to h modulo p. When a solution exists, the smallest non-negative representative in the range zero through p minus two is unique once you fix that range, and it is the value this tool returns.
Unlike ordinary real logarithms, there is no closed-form elementary formula that works for arbitrary primes; the hardness of recovering x for carefully chosen large primes is exactly why discrete-log cryptography is useful. In teaching and in small-parameter experiments, however, you still need a correct, inspectable solver: one that validates the prime hypothesis, reduces inputs into the canonical residue system, searches systematically, and either prints a verifiable exponent or states clearly that no solution exists.
How baby-step giant-step finds x
Baby-step giant-step rewrites the unknown exponent as x equals i times m plus j, where m is roughly the square root of the group order p minus one, and both i and j run from zero up to m. The algorithm first stores every baby value g to the j modulo p in a hash map keyed by residue, then walks giant steps by repeatedly multiplying the target by the modular inverse of g to the m, looking up each intermediate residue in the map.
A hit yields both i and j and therefore x.
Inputs, limits, pricing, and when there is no solution
Required fields are g (base), h (target residue), and p (prime modulus). Digit strings are accepted for large integers within the modulus limit. If h is not in the cyclic subgroup generated by g modulo p—for example when g generates only a proper subgroup and h lies outside it—the solver returns solved false with a null exponent and an explanatory message instead of fabricating a wrong x.
That outcome is a successful computation, not a client error, because the input was well-formed and the mathematical answer is that no logarithm exists. Client errors cover missing fields, non-integers, moduli outside the allowed range, and composite p. The in-browser tool runs the identical library free of charge without an account.
Use the result to check homework, generate known-answer tests for crypto libraries, or explore subgroup membership before scaling parameters in a real protocol design.
What you can do with it
Homework and exam verification
Students and instructors check discrete-log exercises such as 2^x ≡ 5 (mod 13) and receive both the exponent and a printable congruence for the answer key.
Known-answer tests for crypto code
Library authors feed small prime-field instances into CI so modular exponentiation and inverse helpers stay consistent with an independent BSGS reference.
Subgroup membership experiments
Researchers try candidate bases and targets modulo a small prime to see whether h lies in the subgroup generated by g before moving to production-sized parameters.
FAQ
What algorithm do you use?
Baby-step giant-step (Shanks). It finds the smallest non-negative x with g^x ≡ h (mod p) in roughly O(√p) time and memory, after a deterministic primality check on p.
What if no exponent exists?
You get solved: false and x: null with a short message. That is a valid mathematical outcome (h not a power of g mod p), not a billing or validation error.
How do I solve 2^x ≡ 5 (mod 13)?
Enter 2 as the base, 5 as the target and 13 as the prime modulus. The answer is 9: raising 2 to the 9th power and dividing by 13 leaves 5, and no smaller exponent does.
What happens if the modulus is not prime?
The search does not start. The modulus is checked for primality first, and a composite one is refused with a clear message rather than producing an exponent that would mean nothing.
How large can the prime modulus be?
Up to about one trillion. That covers homework, protocol walkthroughs and small experiments while keeping the answer quick; it is not meant for the very large primes used to protect real encryption.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
curl -X POST https://api.kit.forhosting.com/numth/discrete-log \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"g":2,"h":5,"p":13}'const res = await fetch("https://api.kit.forhosting.com/numth/discrete-log", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"g": 2,
"h": 5,
"p": 13
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/discrete-log",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"g": 2,
"h": 5,
"p": 13
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/discrete-log", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"g":2,"h":5,"p":13}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"g":2,"h":5,"p":13}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/discrete-log", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"g": 2,
"h": 5,
"p": 13
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.discrete_log",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Limits
max_p | 1000000000007 |
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
You supply three integers—g, h, and a prime modulus p—and receive a structured JSON answer with the solution, the reduced residues, and a verification equation when a solution exists.
What the discrete logarithm asks for
That is the contract of this endpoint: pure modular arithmetic, no heuristics, and no network calls.
How baby-step giant-step finds x
The method uses on the order of square root of p multiplications and map entries, which is why this capacity caps the prime modulus near one trillion: large enough for homework, protocol walkthroughs, and stress tests of small subgroups, yet bounded so memory and latency stay predictable on a Worker. Before searching, the solver runs a deterministic Miller–Rabin primality test on p; if p is composite, the call fails with invalid_input rather than inventing a log in a structure that is not the prime field multiplicative group. Bases and targets outside zero through p minus one are reduced modulo p, and the response echoes the reduced g, h, and p so callers can audit the exact instance that was solved.
Inputs, limits, pricing, and when there is no solution
Pricing for the API is a flat $0.002 per successful request under the item unit; failed validation is not charged.
Technical questions
How do I solve a discrete logarithm with this API?
POST integers g, h, and prime p to the discrete logarithm endpoint (or use the free browser form). The response includes solved, the exponent x when it exists, reduced residues, and a verification equation.
What happens if p is not prime?
The request fails with invalid_input. This tool defines the discrete log in the multiplicative group of a prime field and will not silently work modulo a composite.
How much does the API cost?
The browser tool is free. The API charges $0.002 per successful request from your prepaid KIT balance; invalid input is not charged. No subscription is required.