Discrete Logarithm Calculator

Calculator Inputs

Use the form below to solve a^x ≡ b (mod m), compare methods, and inspect modular residue patterns.

Base a

Target residue b

Modulus m

Solving method

Search limit

Graph points

Example Data Table

Base a	Target b	Modulus m	Equation	Expected smallest x
2	5	11	2^x ≡ 5 (mod 11)	4
3	13	17	3^x ≡ 13 (mod 17)	4
5	8	23	5^x ≡ 8 (mod 23)	6
10	4	21	10^x ≡ 4 (mod 21)	2

Formula Used

Core problem
Find the smallest nonnegative integer x such that:

a^x ≡ b (mod m)

This calculator solves the discrete logarithm problem in modular arithmetic. You enter a base a, a target residue b, and a modulus m. The goal is to recover the exponent x.

Brute force idea
Compute 1, a, a², a³, ... modulo m until the target residue appears.

Baby-step giant-step idea
Let x = i·n + j where n ≈ √m. Store small powers and match them against larger jumps to reduce the search from linear time to roughly square-root time.

Extended reduction
When gcd(a, m) > 1, the solver first reduces the congruence. If the target fails divisibility tests during reduction, no solution exists.

In practical terms, the calculator uses an extended baby-step giant-step approach for harder cases and can switch to brute force when the chosen range is small enough for direct checking.

How to Use This Calculator

Enter the base value a.
Enter the target residue b.
Enter the modulus m, which must be greater than 1.
Select Auto, Extended Baby-Step Giant-Step, or Brute Force Search.
Set a search limit for preview checks and hit reporting.
Set the number of graph points to visualize residue behavior.
Submit the form to compute the smallest discrete logarithm when it exists.
Review the result card, graph, generated residue table, and export buttons.

Tip: Use a smaller preview range for quick inspection, and use the extended method for larger moduli.

Frequently Asked Questions

1. What does this calculator solve?

It solves equations of the form a^x ≡ b (mod m). The output is the smallest nonnegative exponent x when a valid solution exists.

2. Why can a discrete logarithm fail to exist?

A solution may not exist when the residue b is outside the powers generated by a modulo m. Gcd reductions can also prove impossibility early.

3. What is the difference between brute force and baby-step giant-step?

Brute force checks powers one by one. Baby-step giant-step stores partial results and searches more efficiently, often reducing work to about the square root of the modulus.

4. Does the modulus need to be prime?

No. Prime moduli are common, but this page can also handle many composite cases using an extended reduction stage before the main matching step.

5. What does gcd(a, m) tell me?

It shows whether the base and modulus are coprime. When gcd(a, m) = 1, the modular inverse exists and the main baby-step giant-step stage works directly.

6. Why does the graph matter?

The graph helps you inspect the residue cycle a^x mod m. It makes repeating patterns and target hits easier to see during learning or verification.

7. What does the search limit control?

It limits brute-force exploration and preview hit reporting. Higher values can reveal more repeated matches, but they also increase direct computation time.

8. Can I export the result?

Yes. Use the CSV button for structured data and the PDF button for a printable report containing the result summary and residue information.