Engineering / Mathematics — Discrete Logarithms and Factoring
Brute-Force Discrete Logarithm Search
Exhaustive search for discrete logarithms, its cost, and its role as the baseline against which other methods are measured.
Executive summary
The discrete logarithm can always be found by trying every exponent. The cost is linear in the group order, which is exponential in the bit length.
It establishes the baseline that every better algorithm is measured against, and it is the correct method for very small groups.
Learning objectives
- State the discrete logarithm problem.
- Give the brute-force method and its cost.
- Explain why linear in the group order is exponential.
01The problem
Discrete logarithm
Given a cyclic group G generated by γ and an element α ∈ G, find the integer x with γ^x = α.
The value x is determined modulo the order of γ.
The problem is the inverse of exponentiation, which is easy by repeated squaring. The asymmetry between the two directions is what makes the problem useful cryptographically.
02Exhaustive search
Brute-force discrete logarithm
generator γ, target α, group order qx with γ^x = α- Set β = 1 (the identity).
- For x from 0 to q − 1 where q is the group order:
- If β = α, return x.
- Set β = β · γ.
- Report that α is not in the subgroup generated by γ.
O(q) group operations, O(1) memoryMultiplying by γ at each step rather than recomputing a power keeps each iteration to one group operation. Memory is constant, which is the method's only advantage.
03Why linear is exponential
- Brute force
O(q)Exponential in the bit length of q - Baby step giant step
O(√q) time and memorySquare root; the generic bound - Pollard's rho
O(√q) time, O(1) memorySame time, constant memory - Pohlig-Hellman
O(√q_max)Reduces to the largest prime factor of q - Index calculus
SubexponentialOnly for groups with a factor base, such as Z_p*
For a group of order about 2^256, brute force requires 2^256 operations, which is beyond any conceivable resource. The square-root methods reduce this to 2^128, which is the security level such a group is chosen to provide.
04Frequently asked questions
Why is the discrete logarithm easy in additive groups?
Because exponentiation there is multiplication by an integer, and inverting it is division — a single extended Euclid computation. The hardness of the multiplicative case comes from the group's structure, not from the problem's shape.
Does brute force ever get used?
For very small subgroups, and inside Pohlig-Hellman where the problem has been reduced to groups of small prime order. In those settings it is simpler than the alternatives and fast enough.
What makes elliptic curve groups preferable?
No index calculus method is known for them, so the best attacks are the generic square-root ones. That allows much smaller groups for the same security level — 256 bits rather than 3072.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 270-271.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.