index calculus

Work in Progress

Concept

Index calculus

Correctness claim (index calculus). Smooth relations determine factor-base logarithms, after which one smooth multiple of the target determines its logarithm.

  • layman explanation: factoring smooth values turns products into linear equations for logarithms.

Proof. From ,

After solving these equations, gives

In , collect relations where factors over a small factor base, solve a linear system for the factor-base logarithms, then find a smooth . This subexponential attack is why finite-field Diffie-Hellman needs roughly 3072-bit for 128-bit classical security, while generic elliptic-curve attacks need roughly 256-bit groups.