Engineering / Mathematics — Discrete Logarithms and Factoring
Subexponential Discrete Logarithm Algorithms
Index calculus for discrete logarithms in Z_p*, its two phases, and the precomputation asymmetry it creates.
Executive summary
Index calculus computes discrete logarithms in subexponential time by finding the logarithms of a small factor base first, then expressing an arbitrary target in terms of them.
The expensive first phase depends only on the group, not on the target, so it can be precomputed once and reused against every subsequent target in that group.
Learning objectives
- State the two phases of index calculus.
- Explain why it beats the generic square-root bound.
- Identify the precomputation asymmetry and its consequences.
01The two phases
Choose a factor base
All primes up to a smoothness bound y.
Collect relations
Compute γ^k mod p for random k; keep those results that are y-smooth, each giving a linear relation among the factor base logarithms.
Solve the system
With enough relations, solve the linear system modulo the group order to obtain the logarithm of every factor base element.
Solve for the target
Compute α · γ^s mod p for random s until the result is smooth; then the target's logarithm follows from the known factor base logarithms.
γ^k ≡ ∏ pᵢ^{eᵢ} ⇒ k ≡ Σ eᵢ · log_γ(pᵢ) (mod q)Each smooth power gives one linear equation in the unknown factor base logarithms. Collecting slightly more equations than unknowns determines them all.
02Why it beats the generic bound
Generic algorithms treat the group as a black box and are limited to O(√q). Index calculus uses the fact that elements of Z_p* are integers with factorisations — structure the black-box model forbids.
| Group | Structure available | Best known attack |
|---|---|---|
| Z_p* | Integer factorisation of representatives | Index calculus, L(1/3) |
| Small-characteristic finite fields | Rich; quasi-polynomial methods known | Effectively broken for cryptography |
| General elliptic curves | None exploitable | Generic square root only |
03The precomputation asymmetry
This matters because standardised parameters are shared across an enormous number of deployments. A single precomputation against a common 1024-bit group would compromise every connection using it, and the per-connection cost after that is small.
- Precomputation
L(1/3), very largeOnce per group; reusable indefinitely - Individual logarithm
Much cheaperPer target, after precomputation
The practical responses are to use groups large enough that even the precomputation is infeasible, to avoid widely shared standardised small groups, and to prefer elliptic curves where no such precomputation exists. This reasoning drove the deprecation of 1024-bit finite-field Diffie-Hellman.
04Frequently asked questions
Why collect relations from random powers rather than systematically?
Because smoothness is essentially unpredictable, so random sampling is as good as any strategy and keeps the analysis tractable. The sieving variants generate candidates more efficiently but the principle is the same.
Is the linear algebra step a bottleneck?
Yes, and it is why the smoothness bound cannot simply be raised. The matrix is large and sparse, so specialised sparse solvers over finite fields are used rather than dense Gaussian elimination.
Does the precomputation attack apply to elliptic curves?
No, because there is no index calculus phase to precompute. Each elliptic curve discrete logarithm must be attacked individually at full generic cost, which is a significant structural advantage.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 337-344.
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.