Engineering / Mathematics — Discrete Logarithms and Factoring
Discrete Logarithms in Groups of Prime Power Order
Solving discrete logarithms in a group of prime power order by digit-by-digit lifting.
Executive summary
In a group of order p to the e, the discrete logarithm is recovered one base-p digit at a time, each digit requiring a discrete logarithm in a group of order p only.
The cost is therefore governed by p rather than by the full group order, which is a dramatic reduction when p is small.
Learning objectives
- Derive the digit-by-digit recurrence.
- State the algorithm and its cost.
- Explain the security implication.
01The digit recurrence
Let the group have order p^e and write the unknown logarithm in base p as x = x₀ + x₁p + ... + x_{e−1}p^{e−1}. Raising the equation to a suitable power isolates the lowest unknown digit.
(γ^x)^{p^{e−1}} = (γ^{p^{e−1}})^{x₀} since higher digits contribute exponents divisible by p^eThe element γ^{p^{e−1}} has order p, so this is a discrete logarithm in a group of order p only, solvable by any generic method in O(√p). Once x₀ is known it is stripped off and the process repeats for the next digit.
02The algorithm
Discrete logarithm in a group of order p^e
generator γ of order p^e, target αx with γ^x = α- Set x = 0 and β = α.
- For k from 0 to e−1:
- Compute δ = β^{p^{e−1−k}}, an element of order dividing p.
- Solve the order-p discrete logarithm for δ to obtain the digit x_k.
- Set x = x + x_k · p^k.
- Set β = β · γ^{−x_k p^k}.
- Return x.
O(e · (√p + log(p^e))) group operationsEach of the e digits costs one small discrete logarithm plus some exponentiations. The total is far below the O(p^{e/2}) a generic method on the full group would require.
03Security implication
| Group order | Generic cost | Cost with this method |
|---|---|---|
| q prime, 256 bits | 2^128 | 2^128 — no reduction |
| 2^256 | 2^128 | About 256 tiny steps — trivial |
| p^e, p 64-bit, e = 4 | 2^128 | About 4 × 2^32 — feasible |
This is one half of the Pohlig–Hellman reduction. The other half handles a group whose order has several distinct prime factors, splitting it by the Chinese remainder theorem. Together they mean that security depends entirely on the largest prime factor of the group order.
The practical consequence is that cryptographic groups are chosen to have prime order, or prime order times a very small cofactor, so that no such reduction applies.
04Frequently asked questions
Why solve for the lowest digit first?
Because raising to the power p^{e−1} annihilates the contribution of every higher digit, isolating the lowest one. Working downward from the top would not have this clean separation.
What if the order is not known exactly?
The method needs the exact order and its factorisation. Without them the digit structure cannot be set up, which is another reason parameter generation fixes the group order deliberately.
Is this related to Hensel lifting?
In spirit, yes — both recover a solution digit by digit modulo increasing powers of a prime. The mechanism differs but the pattern of lifting a solution from one power to the next is the same.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 272-274.
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.