Back to Number Theory Dsa

Groups, Primitive Roots & Discrete Logarithms

September 22, 2026 Wasil Zafar 8 min read

Reason about modular operations through finite-group structure.

Table of Contents

  1. Intuition, Vocabulary and Foundations
  2. Step-by-Step Derivations and Algorithms
  3. Implementation, Complexity and Engineering
  4. Applications, Case Studies and Exercises

Intuition, Vocabulary and Foundations

A group is a set with an associative operation, an identity, and an inverse for every element. The nonzero residues modulo a prime $p$ form the multiplicative group $\mathbb F_p^\times$ of size $p-1$. Repeated multiplication by one element is like walking around a circular dial.

Modulo $7$, powers of $3$ are

$$1,3,2,6,4,5,1,\ldots$$

so $3$ generates every nonzero residue and is a primitive root. Powers of $2$ are $1,2,4,1,\ldots$, so $2$ generates only the subgroup $\{1,2,4\}$. The order of $g$ is the least $r\gt0$ satisfying $g^r=e$; Lagrange's theorem gives $r\mid |G|$.

A discrete logarithm reverses exponentiation: given $g,h$, find $x$ with $g^x=h$. Modulo $7$, $3^x\equiv5$ has $x\equiv5\pmod6$, but $2^x\equiv3$ has no solution because $3\notin\langle2\rangle$. Primitive roots do not exist for every composite modulus, so the group domain must be explicit.

A discrete logarithm is relative to the subgroup generated by its base. Determine the exact base order $r$ and verify $h^r=e$ before searching; otherwise “no solution” may be the correct result.

ConceptDefinitionExampleBoundaryQuestion answered
GroupClosed associative operation with identity and inverses$\mathbb F_7^\times$Nonunits modulo $8$ lack inversesIs the algebraic domain valid?
SubgroupSubset that is itself a group$\{1,2,4\}$ modulo $7$$\{1,2,3\}$ is not closedWhich states are reachable?
Element orderLeast $r\gt0$ with $g^r=e$$\operatorname{ord}_7(2)=3$It is not the integer value of $g$When do powers repeat?
Primitive rootGenerator of an entire cyclic group$3$ modulo $7$$2$ modulo $7$ has order $3$Does one element reach everything?
Discrete logarithmSolve $g^x=h$$\log_3 5\equiv5\pmod6$No solution outside $\langle g\rangle$Which exponent produces $h$?
Smooth orderProduct of small prime powers$96=2^5\cdot3$A large prime factor remains difficultWill Pohlig-Hellman help?

Step-by-Step Derivations and Algorithms

To compute the order of $g$ in a finite group of known order $N$, begin with $r=N$. For every prime factor $q$ of $N$, repeatedly test $g^{r/q}=e$. When the equality holds, replace $r$ by $r/q$; otherwise retain that factor. The final value is exact because no remaining prime divisor can be removed.

For prime $p$, a candidate $g$ is primitive exactly when

$$g^{(p-1)/q}\not\equiv1\pmod p$$

for every distinct prime factor $q$ of $p-1$.

Baby-step giant-step writes $x=im+j$ for $m=\lceil\sqrt r\rceil$. Store $g^j$ for $0\le j\lt m$, then inspect $h(g^{-m})^i$. A collision proves $g^{im+j}=h$, reducing exhaustive $O(r)$ work to $O(\sqrt r)$ time and memory.

Pohlig-Hellman factors $r=\prod q_i^{e_i}$, recovers $x$ modulo each prime power through smaller subgroup logarithms, and combines the residues with CRT. Its difficulty is governed chiefly by the largest prime factor of $r$.

Groups, Primitive Roots & Discrete Logarithms algorithm map
flowchart TD
    A["Validate group domain"] --> B["Factor group order N"]
    B --> C["Compute base order r"]
    C --> D{"Target in generated subgroup?"}
    D -->|"No"| E["Report no logarithm"]
    D -->|"Yes"| F{"Is r smooth?"}
    F -->|"No"| G["Baby-step giant-step"]
    F -->|"Yes"| H["Pohlig-Hellman subproblems"]
    H --> I["CRT reconstruction"]
    G --> J["Verify g^x equals h"]
    I --> J

Order reduction is correct because the element order divides the known group order, and every successful division removes a provably unnecessary factor. Baby-step giant-step costs $O(\sqrt r)$ time and memory; Pohlig-Hellman is advantageous only when the exact subgroup order is sufficiently smooth.

Implementation, Complexity and Engineering

This reference targets multiplicative groups modulo a prime. It factors $p-1$, computes exact orders, finds the least primitive root, and solves subgroup logarithms with baby-step giant-step. Membership is checked before the hash table is built, and every candidate is verified.

from math import isqrt

def is_prime(n):
    if n < 2: return False
    if n % 2 == 0: return n == 2
    d = 3
    while d <= n // d:
        if n % d == 0: return False
        d += 2
    return True

def factorize(n):
    if n < 1: raise ValueError("positive integer required")
    result, d = {}, 2
    while d <= n // d:
        while n % d == 0:
            result[d] = result.get(d, 0) + 1
            n //= d
        d = 3 if d == 2 else d + 2
    if n > 1: result[n] = result.get(n, 0) + 1
    return result

def element_order(base, prime):
    if not is_prime(prime): raise ValueError("prime modulus required")
    base %= prime
    if base == 0: raise ValueError("nonzero base required")
    order = prime - 1
    for q in factorize(order):
        while order % q == 0 and pow(base, order // q, prime) == 1:
            order //= q
    assert pow(base, order, prime) == 1
    return order

def primitive_root(prime):
    if not is_prime(prime): raise ValueError("prime modulus required")
    if prime == 2: return 1
    order = prime - 1
    factors = factorize(order)
    for g in range(2, prime):
        if all(pow(g, order // q, prime) != 1 for q in factors):
            return g
    raise ArithmeticError("generator not found")

def baby_step_giant_step(base, target, prime, order=None):
    if not is_prime(prime): raise ValueError("prime modulus required")
    base, target = base % prime, target % prime
    if base == 0 or target == 0: raise ValueError("nonzero elements required")
    actual = element_order(base, prime)
    if order is None: order = actual
    elif order != actual: raise ValueError("incorrect base order")
    if pow(target, order, prime) != 1: return None
    width = isqrt(order)
    if width * width < order: width += 1
    baby, value = {}, 1
    for j in range(width):
        baby.setdefault(value, j)
        value = value * base % prime
    factor = pow(pow(base, width, prime), -1, prime)
    value, best = target, None
    for i in range(width + 1):
        if value in baby:
            candidate = (i * width + baby[value]) % order
            if pow(base, candidate, prime) == target:
                best = candidate if best is None else min(best, candidate)
        value = value * factor % prime
    return best

if __name__ == "__main__":
    assert factorize(96) == {2: 5, 3: 1}
    assert primitive_root(7) == 3
    assert element_order(3, 7) == 6
    assert element_order(2, 7) == 3
    assert baby_step_giant_step(3, 5, 7) == 5
    assert baby_step_giant_step(2, 4, 7) == 2
    assert baby_step_giant_step(2, 3, 7) is None
    p, secret = 101, 73
    g = primitive_root(p)
    h = pow(g, secret, p)
    assert baby_step_giant_step(g, h, p) == secret
    print("all tests passed")
MethodRequired informationTimeMemoryFailure modeMitigation
Exhaustive powersValid group operation$O(r)$$O(1)$Too slow for large $r$Use as a small oracle
Order reductionFactorization of group orderModular exponentiationsFactor listIncomplete factorizationVerify the final retained factors
Primitive-root searchPrime modulus and factors of $p-1$Candidate-dependentFactor listAssuming a composite domain is cyclicRestrict the API to proven domains
Baby-step giant-stepExact subgroup order$O(\sqrt r)$$O(\sqrt r)$Target outside subgroupCheck membership first
Pollard rho logarithmSuitable subgroupExpected $O(\sqrt r)$$O(1)$Degenerate random walkRetry independently
Pohlig-HellmanComplete factorization of $r$Prime-power dependentInner-solver dependentLarge prime factor dominatesUse BSGS or rho for that factor

Applications, Case Studies and Exercises

Element orders determine cycle lengths in modular state machines and subgroup protocols. A safe system treats the modulus, group, base order, and target membership as validated metadata rather than untyped integers.

Practice

Apply Groups, Primitive Roots & Discrete Logarithms

Generator audit: modulo $23$, factor $22=2\cdot11$. For $g=5$, check $g^{11}\not\equiv1$ and $g^2\not\equiv1$, then list its powers to confirm order $22$.

Subgroup-safe logarithm: modulo $29$ with base $4$, compute $r=\operatorname{ord}_{29}(4)$. Test $h^r\equiv1$ before invoking baby-step giant-step. Verify every returned $x$ by recomputing $4^x$.

Hands-on engine: implement order, primitive-root, and discrete-log commands. For every prime $p\le200$, compare with exhaustive enumeration. Benchmark time and table size as $r$ grows. Success requires exact agreement and explicit no-solution results.

Exercises: list subgroups generated by $2$ and $3$ modulo $7$; find all primitive roots modulo $11$; trace BSGS for $2^x\equiv15\pmod{29}$; explain membership failures; apply Pohlig-Hellman to order $72$; implement a memory-light Pollard-rho solver.

Use order reduction after factoring the group order, primitive-root tests only on proven cyclic domains, baby-step giant-step for a generic time-memory trade-off, and Pohlig-Hellman when the subgroup order is smooth. Always validate subgroup membership and verify $g^x=h$.

Next in the Series

In Linear Recurrences, Matrices & Generating Functions, we'll explore Accelerate recurrence evaluation with algebraic representations..

Continue the Series

Modular Arithmetic & Fast Exponentiation

Compute safely and efficiently in residue classes.

Read Article
Primality Testing & Integer Factorization

Test and factor large machine integers robustly.

Read Article