Skip to content
Tutorials Center
My learning

Topics

Lesson 191 of 225 ยท Math and Bit Manipulation

Primitive Roots and Discrete Logarithm (Baby-Step Giant-Step)

Find multiplicative orders and primitive roots modulo a prime, then solve a^x = b mod p with the baby-step giant-step algorithm in O(sqrt p) time in Python.

Fast exponentiation computes g^x mod p quickly. The reverse problem is believed to be hard: given g, h and p, find x such that g^x = h (mod p). This is the discrete logarithm. Its difficulty protects Diffie-Hellman key exchange and many other protocols, yet for the small moduli of contests and exercises, an elegant O(sqrt p) algorithm solves it: baby-step giant-step.

To use it well you need two ideas first: the order of a number modulo p, and primitive roots, special numbers whose powers hit every non-zero residue. We build both from scratch, test them with brute force, and then split the exponent in two to get the square-root speedup. You should be comfortable with fast exponentiation and number theory.

Order and primitive roots

Let p be prime and g not divisible by p. By Fermat's little theorem g^(p-1) = 1 (mod p). The order of g is the smallest k > 0 with g^k = 1. The order always divides p - 1.

A primitive root modulo p is a number whose order is exactly p - 1. Its powers g^0, g^1, ..., g^(p-2) run through every residue 1..p-1 once. For p = 7, the number 3 is a primitive root: 3, 2, 6, 4, 5, 1.

Primitive roots exist for every prime (and for 2, 4, p^k, 2p^k), and there are phi(p - 1) of them. The smallest one is usually tiny, so a search from 2 upward finds it fast.

To test a candidate g without computing the full order: factor p - 1, and check that g^((p-1)/q) != 1 for every prime factor q of p - 1. If any equals 1, the order is a proper divisor of p - 1.

Python Order and primitive roots

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The order function starts from p - 1 and strips prime factors while the power still equals 1, which keeps the loop to O(log p) modular powers.

Why a primitive root helps

If g is a primitive root, every residue h in 1..p-1 equals g^x for exactly one x in 0..p-2. That x is the index (or discrete log) of h. Indices turn multiplication into addition, exactly as logarithms do: index(a*b) = index(a) + index(b) (mod p-1). Number-theoretic transforms rely on this to find roots of unity, as in FFT and polynomials.

With small p you can build a lookup table power -> index by walking through the powers once.

The discrete logarithm problem

Given g, h, p, find the smallest x >= 0 with g^x = h (mod p), or report that none exists. The naive loop multiplies by g up to p - 1 times: O(p).

Python Naive discrete log

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Baby-step giant-step

Split the unknown x into two parts using m = ceil(sqrt(p)):

TEXT
x = i * m - j        with 1 <= i <= m  and  0 <= j < m

The equation g^x = h becomes

TEXT
g^(i*m)  =  h * g^j     (mod p)

The right side depends only on j (the baby steps: small shifts of h), the left side only on i (the giant steps: jumps of size m). So:

  1. Store h * g^j for all j = 0..m-1 in a dictionary, value -> j.
  2. For i = 1..m, compute g^(i*m) and look it up. A hit gives x = i*m - j.

Both phases take m steps, so the total is O(sqrt p) time and O(sqrt p) memory, versus O(p) for the naive loop.

flowchart LR
  A["Baby steps: store h*g^j<br/>for j = 0..m-1"] --> C{"g^(i*m) in table?"}
  B["Giant steps: i = 1..m,<br/>compute g^(i*m)"] --> C
  C -->|yes| D["x = i*m - j"]
  C -->|no| E["no solution"]

Meet in the middle: the baby-step table is searched by the giant steps.

The same "meet in the middle" idea appears in meet-in-the-middle for subset sums.

Python Baby-step giant-step

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Keeping the largest j per table value (as the loop does by overwriting) gives the smallest x because x = i*m - j. For p near one billion, m is about 31,623, so the whole search takes a fraction of a second, while the naive loop would need a billion steps.

Order of a base that is not a primitive root

BSGS works for any base g coprime to p, not only primitive roots. If h is not a power of g, the algorithm simply finds no match and returns None. If the modulus is not prime, or gcd(g, m) > 1, the standard extension first divides out the common factor from both sides; the idea is the same but the details are fiddlier, so check your problem's constraints.

Complexity summary

Task Time Memory
Order of g mod prime p (with factored p-1) O(log^2 p) O(1)
Find the smallest primitive root about O(log^2 p) per candidate, few candidates O(1)
Discrete log, naive O(p) O(1)
Discrete log, baby-step giant-step O(sqrt p) O(sqrt p)

Common mistakes:

  • Using m smaller than sqrt(p), which leaves some exponents uncovered.
  • Starting giant steps at i = 0: then x = 0 - j could be negative. Start at i = 1.
  • Forgetting the special case h = 1 (answer 0).
  • Applying the primitive-root test with p composite or without factoring p - 1.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the order of 2 modulo 7?

    The powers of 2 modulo 7 are 2, 4, 1, so the smallest k with 2^k = 1 is 3. It divides p - 1 = 6 as every order must.
  2. 2. How do you test that g is a primitive root modulo a prime p?

    If the order were a proper divisor of p - 1, it would divide (p-1)/q for some prime q, making that power equal to 1.
  3. 3. In baby-step giant-step, how many entries are stored and how many lookups are done for modulus p?

    With m = about sqrt(p), the table of baby steps has m entries and there are m giant steps, so both phases cost O(sqrt p).
  4. 4. Why do the giant steps start at i = 1 instead of i = 0?

    With i = 0 the formula gives x = -j, which is not a valid exponent. The case x = 0 means h = 1 and is checked on its own.

Summary

  • The order of g modulo p is the smallest k with g^k = 1; it divides p - 1. A primitive root has order p - 1.
  • Test a primitive root by checking g^((p-1)/q) != 1 for every prime q dividing p - 1.
  • The discrete logarithm solves g^x = h (mod p); the naive search is O(p).
  • Baby-step giant-step writes x = i*m - j with m = ceil(sqrt p), stores h*g^j in a dictionary and scans g^(i*m): O(sqrt p) time and memory.
  • Handle h = 1 separately, and remember that no solution may exist.

Next: Chinese Remainder Theorem