Index calculus stops treating every group element as an unrelated black box. It exploits the fact that elements of a finite field can often be represented by small factors whose logarithms can be learned once and reused.
The algorithm has two very different phases. First, collect many smooth relations and solve for the logarithms of a factor base. Second, express a new target in terms of those known logarithms. The expensive precomputation can then serve many individual logarithm queries in the same field and subgroup.
This is Guide 27 in the Bukit Timah Tutor Computational Number Theory series. It deepens the index-calculus overview in Guide 6 and uses exact modular linear algebra from Guide 18.
1. The setting
Work in F_p* with primitive root g and order N=p−1. Given h, we want
g^x ≡ h (mod p).
A generic algorithm only uses the group operation. Index calculus uses the representation of residues as ordinary integers that may factor into small primes.
This extra structure is why index calculus can beat generic square-root algorithms in suitable finite fields.
2. Choose a factor base
Select small primes
B={p1,p2,...,pm}.
The aim is to determine
log_g(p1),...,log_g(pm) modulo N.
A residue is B-smooth if its integer representative factors completely over the base.
Larger factor bases increase smoothness probability but also create a larger linear system.
3. Relation collection
Choose exponents k and compute
g^k mod p.
If the residue is B-smooth, say
g^k ≡ p1^e1 ... pm^em (mod p),
then taking discrete logarithms gives the linear congruence
k ≡ e1 L1 + ... + em Lm (mod N),
where L_i=log_g(p_i).
Collect enough independent relations to solve for the unknown factor-base logs.
4. Worked field: F29*
Take p=29 and g=2. The element 2 has order28, so every logarithm is modulo28.
Choose factor base
B={2,3,5,7}.
We know immediately
L2=log_2(2)=1.
Now collect three more smooth relations.
5. Relation one: recover log 3
Compute
2^8 mod29 =24 =2³·3.
Taking logs:
8 ≡3L2+L3 (mod28).
Since L2=1:
L3 ≡8−3 =5 (mod28).
Indeed 2^5=32≡3 mod29.
6. Relation two: recover log 7
Compute
2^17 mod29 =21 =3·7.
Therefore
17 ≡L3+L7 (mod28).
Using L3=5:
L7 ≡12 (mod28).
Check: 2^12≡7 mod29.
7. Relation three: recover log 5
Compute
2^23 mod29 =10 =2·5.
So
23 ≡L2+L5 (mod28).
Hence
L5 ≡22 (mod28).
Check: 2^22≡5 mod29.
8. The factor-base logarithm table
prime 2 3 5 7 log base2 1 5 22 12 (mod28)
The precomputation phase is complete for this tiny factor base.
In a realistic computation, hundreds, thousands or millions of relations may be required, and the relation matrix is sparse.
9. Solve an individual logarithm
Now find log_2(11) modulo29.
Multiply the target by a random power of g until the result is smooth:
11·2² =44 ≡15 (mod29) 15=3·5.
Taking logarithms:
log_2(11)+2 ≡L3+L5 (mod28)
≡5+22
≡27.
Therefore
log_2(11) ≡25 (mod28).
Verification:
2^25 mod29 =11.
10. Precomputation and query phases are different jobs
The relation collection and linear algebra depend on the field, generator and subgroup. Once completed, they can be reused for many targets.
The individual logarithm phase should therefore be costed separately. In a setting with many targets in the same group, expensive precomputation may become worthwhile.
This is an important difference from baby-step giant-step or Pollard rho, which primarily attack one target at a time.
11. Relation matrices
Write each smooth relation as a row of exponent coefficients:
[e1 e2 ... em] · [L1 ... Lm]^T ≡ k (mod N).
Stack the rows into
A L ≡ b (mod N).
The matrix is sparse because each smooth integer usually uses only a small fraction of the factor-base primes.
Finding enough rows is not the same as finding enough independent rows.
12. The modulus p−1 is usually composite
Linear algebra modulo N=p−1 is not automatically linear algebra over a field.
A pivot may fail to be invertible. Dividing a congruence by a nonunit can lose or multiply solutions.
One robust approach factors N into prime powers, solves the relation system modulo each prime-power factor and reconstructs factor-base logs with CRT. Another uses integer normal-form techniques that preserve exact divisibility information.
This is where Pohlig–Hellman and Smith/Hermite normal forms connect directly to index calculus.
13. Why smoothness probability controls the search
If residues near size p are required to factor only over primes ≤B, many candidates will fail.
Increasing B makes smooth values more common but increases the number of unknown factor-base logs and therefore the matrix dimension.
The algorithm’s subexponential complexity emerges from balancing smoothness probability against relation-system size.
14. Sieving for relations
Instead of factoring every random residue from scratch, structured index-calculus variants sieve ranges or polynomial values for divisibility by factor-base primes.
Each small prime contributes to predictable arithmetic progressions. Accumulated logarithmic scores identify candidates likely to be smooth.
This is the same general performance idea seen in the quadratic sieve: exploit where small factors must occur instead of rediscovering them by repeated trial division.
15. Large-prime variants
A candidate that factors over the base except for one moderately larger prime can be retained as a partial relation.
Two partial relations containing the same large prime can be combined so that its exponent cancels or becomes manageable.
Allowing one or two large primes can raise relation yield dramatically, at the cost of graph-style matching and more filtering.
16. Filtering before linear algebra
Raw relation data contains duplicates, columns appearing only once, dependent structures and partial-relation components.
Filtering removes unusable data and performs controlled elimination to reduce the final matrix while preserving the logarithm information needed.
For large computations, good filtering can be as important as faster matrix multiplication.
17. Sparse modular linear algebra
Dense Gaussian elimination is unsuitable for very large sparse relation matrices.
Block Lanczos, block Wiedemann and related Krylov-space methods use repeated sparse matrix-vector products.
The exact field or ring in which the matrix is solved depends on the subgroup order and decomposition strategy.
18. Individual logarithm by randomisation
The worked example used
h g^t
and searched for a smooth representative.
If
h g^t ≡ product p_i^e_i,
then
log_g(h) ≡ Σe_i L_i − t (mod N).
This is the simplest individual-log descent.
19. When one-step smoothness is unlikely
For large fields, forcing the target directly into the small factor base can be too expensive.
Instead use a descent: rewrite the target in terms of somewhat smaller-degree or smaller-norm objects, then recursively rewrite those objects until every leaf has a known factor-base logarithm.
This idea becomes central in NFS-DL, the topic of Guide 28.
20. Factor-base choice
A factor base should contain elements that are easy to recognise in relations, numerous enough to give reasonable smoothness probability and small enough to keep the linear system manageable.
In prime fields, small rational primes are the classical choice. In extension fields or number-field algorithms, factor-base elements become irreducible polynomials or prime ideals.
The object changes; the relation principle remains.
21. Complexity and the importance of representation
Generic algorithms see only N group elements and therefore face square-root barriers in the generic group model.
Index calculus escapes that model by exploiting representation. Finite-field elements can factor into smaller algebraic objects and yield additive logarithm relations.
This explains why index calculus applies powerfully in many multiplicative finite fields but has no direct analogue of the same strength for generic elliptic-curve groups.
22. Verification receipts
For every relation, retain k, the residue g^k mod p and its exact factorisation over the allowed base.
For the solved factor-base table, verify each p_i by checking
g^(L_i) ≡ p_i (mod p).
For an individual logarithm, retain the randomisation exponent t and the exact smooth factorisation of h g^t.
Finally verify g^x=h.
23. Common mistakes
1. Treating every relation as independent. 2. Solving modulo p instead of modulo the group order p−1. 3. Using field-style pivot inversion modulo a composite N without checking gcd. 4. Recording approximate rather than exact factorisations.
5. Mixing partial relations with full relations without eliminating their large primes. 6. Forgetting the −t term in the individual-log equation. 7. Assuming precomputation is free when comparing one-off attacks. 8. Applying finite-field index-calculus complexity claims to arbitrary groups.
24. Practice set
1. Define a factor base. 2. Define B-smoothness. 3. Derive the logarithm relation from g^k=∏p_i^e_i. 4. What is the exponent modulus in F29*?
5. Use 2^8≡24 to find log_2(3). 6. Use 2^17≡21 to find log_2(7). 7. Use 2^23≡10 to find log_2(5). 8. Write the factor-base log table.
9. Use 11·2²≡15 to find log_2(11). 10. Verify the answer. 11. Why is relation collection reusable? 12. Why is linear algebra mod28 subtle?
13. What is a large-prime partial relation? 14. What is filtering for? 15. Why is a descent needed for large individual logarithms? 16. Why can index calculus beat generic square-root methods?
25. Answers
1. A selected set of small elements whose logs become the relation-system unknowns. 2. Complete factorisation over that set. 3. k≡Σe_i log_g(p_i) modN. 4. 28.
5. 5. 6. 12. 7. 22. 8. For 2,3,5,7 the logs are 1,5,22,12 modulo28.
9. log_2(11)+2≡5+22, so log_2(11)=25 mod28. 10. 2^25≡11 mod29. 11. It depends on the field/base, not on one target. 12. 28 is composite, so nonzero pivots need not be invertible.
13. A relation smooth except for one controlled larger factor. 14. Reduce raw relation data while preserving the useful linear dependencies. 15. Direct target smoothness becomes too rare. 16. It exploits field representation and factorisation structure unavailable to a generic group algorithm.
Sources and further study
Victor Shoup, A Computational Introduction to Number Theory and Algebra, gives a rigorous computational treatment of finite fields and discrete logarithms. Alfred Menezes, Paul van Oorschot and Scott Vanstone, Handbook of Applied Cryptography, surveys index-calculus methods, factor bases and discrete-log algorithms.
Continue through Batch 07
Return to Guide 26: Pollard Rho. Continue to Guide 28: Number Field Sieve for Discrete Logarithms, Virtual Logs and Descent.