Bukit Timah Tutor

Bukit Timah Tutor

Small Group Tutorials

WhatsApp Us

Here to help students catch up, keep up, and move ahead. Book a consultation here.

Computational Number Theory 6: Discrete Logarithms, Baby-Step Giant-Step and Pollard Rho

The discrete logarithm problem reverses modular exponentiation: given g, h and a modulus or finite group, recover an exponent x such that g^x=h.

Forward exponentiation is efficient because binary exponentiation evaluates g^x in logarithmically many group operations. Reversing that map is different. In a large cyclic group, trying exponents one by one is expensive, and no classical algorithm is known that solves every large discrete logarithm problem in polynomial time.

This guide builds the problem carefully: group order, element order, existence and uniqueness, exhaustive search, baby-step giant-step, smooth-order reduction and Pollard rho. The objective is mathematical understanding of the algorithms and their complexity.

This is Guide 6 in the Bukit Timah Tutor Computational Number Theory series. Use the BTT Mathematics Hub for the wider Mathematics route.

Forward map → group structure → inverse search → collision → linear relation → verification.

1. Start with a cyclic group

Let G be a finite cyclic group generated by g. Every element of G can be written as g^x for some integer x. If |G|=N, then exponents are naturally considered modulo N because g^N is the identity.

The discrete logarithm of h to base g is an exponent x satisfying g^x=h. We may write x=log_g h, but this is not an ordinary real logarithm. It is an inverse problem inside a finite group.

2. Example modulo a prime

Modulo the prime 23, the nonzero residues form a multiplicative group of order 22. The element 5 has order 22 and is therefore a generator.

Suppose we want x such that

5^x≡8 (mod 23).

Direct inspection gives 5²≡2, 5³≡10, 5⁴≡4, 5⁵≡20 and 5⁶≡8. So x≡6 (mod 22).

This small example hides the computational issue. If the group order has hundreds of bits, checking x=0,1,2,… is not a useful general algorithm.

3. Existence depends on subgroup membership

If g does not generate the whole group, then only elements in the subgroup ⟨g⟩ can have a logarithm to base g.

If ord(g)=r, then the powers of g repeat every r steps. A solution x, when it exists, is unique modulo r. Therefore the correct modulus for the exponent is the order of g, not automatically the order of the ambient group.

4. Element order

The order ord(g) is the least positive r such that g^r=e, where e is the identity. Lagrange’s theorem says r divides |G|.

When the factorisation of |G| is known, the order can often be determined by testing divisors. Start with r=|G| and repeatedly ask whether g^(r/q)=e for prime divisors q of r. If so, replace r by r/q and continue.

This preprocessing matters because a discrete logarithm algorithm should work in the smallest group that actually contains the problem.

5. Brute force

value = identity
for x = 0,1,...,r−1:
    if value = h:
        return x
    value = value·g

The algorithm is exact and uses little memory, but its worst-case work is O(r) group operations. If r is approximately 2^k, that is exponential in the k-bit description of the group order.

6. Time–memory tradeoff

Baby-step giant-step reduces the O(r) search to about O(√r) group operations by storing one side of a meet-in-the-middle equation.

Let m=⌈√r⌉ and write the unknown exponent as

x=im+j with 0≤i,j<m.

Then g^(im+j)=h implies

g^j=h·(g^(−m))^i.

The left side generates baby steps. The right side generates giant steps. A collision reveals i and j.

7. Baby-step giant-step algorithm

m = ceil(sqrt(r))
store g^j for j=0,...,m−1 in a lookup table
factor = g^(−m)
gamma = h

for i=0,...,m−1:
    if gamma appears as g^j:
        return x = im+j mod r
    gamma = gamma·factor

The method uses O(√r) stored group elements and O(√r) group operations, ignoring logarithmic factors for table lookup and arithmetic.

8. Worked baby-step giant-step: 5^x≡8 mod 23

The order is r=22, so m=⌈√22⌉=5.

Baby steps:

j=0: 5^0 ≡ 1
j=1: 5^1 ≡ 5
j=2: 5^2 ≡ 2
j=3: 5^3 ≡ 10
j=4: 5^4 ≡ 4   (mod 23)

Now 5^5≡20. Its inverse modulo 23 is 15 because 20·15=300≡1. So the giant-step factor is 15.

i=0: gamma=8
 i=1: gamma=8·15≡5

The value 5 matches baby step j=1. Therefore x=1·5+1=6. Check: 5^6≡8.

9. Why meet-in-the-middle works

A one-dimensional search over r possibilities is rewritten as two searches over approximately √r possibilities. The equation x=im+j is not special to logarithms; meet-in-the-middle techniques recur throughout algorithms whenever an unknown can be decomposed into two smaller coordinate ranges.

10. Memory is the price

Baby-step giant-step achieves its speed by storing roughly √r group elements. For very large r, that memory requirement can become the limiting resource even when the number of group operations is acceptable.

This motivates collision algorithms that keep the √r running-time scale while using essentially constant memory.

11. Pollard rho for discrete logarithms

Pollard rho constructs a pseudorandom walk through the group. Each state is represented in the form

X=g^a h^b.

The group is partitioned into a few subsets. Depending on which subset X lies in, the algorithm might multiply by g, multiply by h, or square X. At the same time it updates the exponents a and b so the representation remains correct.

A cycle-finding method detects when two walk states collide.

12. How a collision becomes a linear congruence

Suppose

g^a h^b = g^A h^B.

If h=g^x, then

g^(a+bx)=g^(A+Bx).

Working modulo r=ord(g),

(b−B)x≡A−a (mod r).

This is a linear congruence. If b−B is invertible modulo r, solve immediately. If not, the gcd conditions from Guide 1 determine whether the collision yields one, several or no candidate logarithms.

13. Constant memory, probabilistic path

Pollard rho for logarithms has expected running time on the order of √r group operations under the random-walk model while using very little memory. Different walks can be restarted if a collision produces a degenerate congruence.

The algorithm is randomized in discovery, but any returned logarithm is checked deterministically by computing g^x and comparing with h.

14. Distinguished points and parallel search

Large collision searches can record only states satisfying a simple recognisable property, called distinguished points. Walks can then be distributed across workers, and collisions are found by comparing the much smaller set of distinguished endpoints.

This is an example of algorithmic architecture: preserve enough information to detect useful collisions without storing every state encountered.

15. Smooth group order changes the problem

If the group order r factors into small prime powers, the discrete logarithm can often be decomposed into smaller logarithms. This is the idea behind the Pohlig–Hellman algorithm.

Suppose

r=∏q_i^{e_i}.

The unknown x can be determined modulo each q_i^{e_i} by projecting into appropriate subgroups. The separate congruences for x are then recombined by the Chinese Remainder Theorem.

The difficulty is therefore governed strongly by the largest prime factor of the group order, not merely by the total order itself.

16. A structural workflow for discrete logs

  1. Determine the group and the order of the base element g.
  2. Check that h belongs to ⟨g⟩.
  3. Factor the group or subgroup order if feasible.
  4. If the order is smooth, decompose with Pohlig–Hellman ideas.
  5. For a large prime-order component, choose baby-step giant-step when memory is acceptable or Pollard rho when memory is scarce.
  6. Recombine component answers with CRT if needed.
  7. Verify the candidate by exponentiation.

17. Discrete logs in different groups

The phrase “discrete logarithm problem” describes a family of inverse problems, not one fixed modulus. It can be posed in multiplicative groups modulo primes, subgroups of finite fields, elliptic-curve groups and other finite cyclic structures.

The generic algorithms—brute force, baby-step giant-step and Pollard rho—depend mainly on group operations. Other algorithms exploit extra algebraic structure available only in particular groups.

18. Generic versus structure-specific algorithms

A generic algorithm treats group elements as opaque objects that can be multiplied, inverted and compared. In that model, square-root-style complexity is fundamental for the best broad classical methods.

Some finite-field groups permit index-calculus methods that exploit the representation of elements and smoothness relations. Those methods can outperform generic √r search. The lesson is the same one encountered in factorisation: extra structure can change the algorithmic landscape.

19. Verification and failure states

  • Candidate x: verify g^x=h.
  • No logarithm: show h is outside the subgroup generated by g.
  • Pollard degenerate collision: restart or solve the resulting noninvertible linear congruence carefully.
  • Multiple representatives: normalise x modulo ord(g).
  • Wrong ambient modulus: remember that exponent periodicity is controlled by element order.

20. Complexity perspective

If a subgroup has prime order r≈2^k, baby-step giant-step and Pollard rho require about √r≈2^(k/2) group operations. That is a dramatic improvement over 2^k exhaustive search, but it is still exponential in the bit length k.

Quantum order-finding techniques change the theoretical model: Shor-type algorithms solve discrete logarithms in important finite abelian groups in polynomial time on an ideal fault-tolerant quantum computer. As with factoring, computational hardness depends on the computational model.

21. Common mistakes

  • Assuming a logarithm always exists. Check subgroup membership.
  • Using the ambient group order instead of ord(g). Exponent uniqueness is modulo the base element’s order.
  • Calling baby-step giant-step O(log r). Its search size is O(√r), not logarithmic.
  • Ignoring memory. BSGS stores O(√r) elements.
  • Treating a Pollard collision as automatically solvable. The coefficient of x may share a gcd with r.
  • Forgetting verification. A proposed logarithm is checked cheaply with fast exponentiation.

22. Practice set

  1. Find x with 5^x≡8 (mod 23).
  2. Find x with 2^x≡15 (mod 29).
  3. Explain why exponents are considered modulo ord(g).
  4. For a group order r=101, what m would BSGS use?
  5. State the baby-step and giant-step equation.
  6. Explain the time–memory tradeoff of BSGS.
  7. In a Pollard-rho collision g^a h^b=g^A h^B, derive the congruence for x.
  8. What should be done if b−B is not invertible modulo r?
  9. Why is a smooth group order helpful?
  10. What role does CRT play in Pohlig–Hellman?
  11. Why can Pollard rho be preferable to BSGS for large groups?
  12. How is a claimed discrete logarithm verified?

23. Answers and checks

1. x≡6 (mod 22).

2. x≡27 (mod 28), because 2^27≡15 (mod 29).

3. If ord(g)=r, then g^(x+r)=g^x g^r=g^x, so logarithms repeat modulo r.

4. m=⌈√101⌉=11.

5. Write x=im+j and solve g^j=h(g^(−m))^i.

6. It reduces time from O(r) to O(√r) but requires O(√r) stored group elements.

7. Substituting h=g^x gives (b−B)x≡A−a (mod r).

8. Solve it as a general linear congruence using gcd conditions; if the collision is degenerate, restart the walk.

9. It allows the logarithm to be decomposed into smaller prime-power subgroup logarithms.

10. CRT recombines x modulo the prime-power factors of the group order into x modulo the full order.

11. It keeps expected O(√r) work while using essentially constant memory instead of a √r table.

12. Compute g^x and check that the result equals h.

24. Continue the series

Return to the Singapore Mathematics Hub for the complete public Mathematics estate.