Baby-step giant-step calculator for discrete logarithms
2 raised to the 9th power leaves a remainder of 5 when divided by 13, so the discrete logarithm of 5 to base 2 modulo 13 is 9. Enter a base, a target and a modulus, prime or composite, to find the exponent. 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
- N
- 13
- X
- 9
- Equation
- 2^9 ≡ 5 (mod 13)
This baby-step giant-step calculator finds a non-negative exponent x that makes g raised to x congruent to h modulo n. Unlike a solver restricted to prime fields, it also handles composite moduli and bases that are not coprime to the modulus by reducing the equation before the main search. The result includes normalized residues and a readable verification equation.
Describe the modular equation precisely
Provide three integers: g is the generator or base, h is the target, and n is the modulus. The calculator seeks a non-negative x satisfying g^x congruent to h modulo n. Negative bases and targets are accepted and normalized into the standard residue interval from zero through n minus one before calculation.
The modulus must be at least two and may be prime or composite, up to the published limit. Exponent zero is considered first, following the usual convention that g^0 is one modulo n. Therefore a target congruent to one produces x equal to zero immediately.
Understand the baby and giant steps
A direct search tries exponents one after another and can require a number of modular multiplications proportional to the modulus. Baby-step giant-step trades memory for speed. It selects a width near the square root of the search range, records consecutive small powers of the base as baby steps, and then advances through the target in jumps of that width.
A matching residue combines a giant-step index with a baby-step index to recover an exponent. Both the table size and the number of jumps are therefore on the order of the square root of n. This implementation is deterministic: it does not sample candidates, depend on random seeds, contact a service, or use the clock.
For non-coprime inputs it first applies the extended form of the algorithm. Common divisors are removed from the congruence one at a time while an exponent offset and multiplier are tracked. If a divisor makes the target unreachable, the solver can reject the equation immediately.
Once the reduced base is invertible, the ordinary hash-table search begins, and the final offset is added back. The returned candidate is independently checked by modular exponentiation before it leaves the library.
Limits and cases without a solution
A discrete logarithm does not necessarily exist. The powers of g may visit only part of the residues modulo n, leaving h outside the generated sequence. Malformed integers, missing fields, a modulus below two, and a modulus above the declared bound produce the same client-facing error category with more specific messages.
Computational cost grows with the square root of the reduced modulus because the algorithm builds an in-memory table, so the cap prevents unexpectedly large allocations and keeps execution bounded. Use modest parameters for teaching, test-vector construction, puzzle solving, and diagnostic work. This is not a way to recover secrets from production cryptographic groups, whose sizes are deliberately far beyond this search limit.
What you can do with it
Verify modular arithmetic exercises
Check a classroom equation and receive both the exponent and a readable congruence that can be substituted back into the problem.
Build deterministic test vectors
Generate known answers for modular exponentiation code, including cases with composite moduli and shared factors.
FAQ
Does the modulus have to be prime?
No. The extended reduction supports prime and composite moduli, including many cases where g and n share a factor.
Which exponent is returned?
The solver searches non-negative exponents, handles exponent zero explicitly, and returns a verified solution found by the deterministic reduction and BSGS search.
Why is there a modulus limit?
Baby-step giant-step uses square-root memory as well as square-root time. The bound keeps the hash table and execution time predictable.
What if no exponent exists?
The powers of the base may reach only some of the remainders modulo n, so the target can be out of reach. In that case you get a clear message that no exponent exists, not an empty or misleading answer.
Why is this faster than trying exponents one by one?
A direct search may need as many steps as the modulus. This method stores a table of small powers and then jumps through the target in large strides, so both parts take roughly the square root of n.
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/baby-step-giant-step \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"g":2,"h":5,"n":13}'const res = await fetch("https://api.kit.forhosting.com/numth/baby-step-giant-step", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"g": 2,
"h": 5,
"n": 13
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/baby-step-giant-step",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"g": 2,
"h": 5,
"n": 13
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/baby-step-giant-step", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"g":2,"h":5,"n":13}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"g":2,"h":5,"n":13}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/baby-step-giant-step", 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,
"n": 13
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.baby_step_giant_step",
"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_n | 1000000000000 |
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
If the target is not reachable from the supplied generator, the request returns a clear input error instead of an ambiguous empty result, making the capability convenient for scripts, lessons, and repeatable mathematical checks.
Describe the modular equation precisely
Inputs may be JSON integers or digit strings, which is useful when a value is awkward to represent directly in a client language. The response echoes those normalized values, so the exact equation being solved remains visible even when the original input was outside that interval. A successful response contains x, the normalized operands, the method name, and a plain verification equation. This makes the output easy to inspect manually and straightforward to assert in automated tests without reconstructing display text in every calling application.
Handle limits, failures, and API use
In that case this capability raises an invalid_input error whose message states that no exponent exists. That behavior is intentional and is useful in pipelines where absence of a logarithm should stop the next step; callers can handle the standard error code without inspecting nullable result fields. Browser execution uses the same pure solver as the API. Automated API calls cost $0.002 per item, while the page can be used interactively without introducing network-dependent arithmetic or nondeterministic results.
Integration use cases
Detect unreachable targets
Use the standard invalid_input failure to stop a workflow when a target does not belong to the power sequence generated by g.
Technical questions
What happens when there is no discrete logarithm?
The call fails with invalid_input and a message saying that no exponent exists for the supplied values.
How much does an API call cost?
Each item costs $0.002. The browser runner uses the same pure library for interactive calculations.