Discrete Logarithms

• Shanks baby-step giant-step algorithm
• Pollard rho algorithm
• Polhig-Hellman algorithm
• Index calculus method using either the Gaussian integer sieve or linear sieve (for prime fields $\mbox{\rm GF}(p)$).

The index calculus method applied to an arbitrary field $\mbox{\rm GF}(p)$, where p is a 100-bit prime such that (p-1)/2 is prime (the worst case), takes 10 seconds to perform the sieving and about 0.8 seconds to compute an individual logarithm. For a 20-decimal-digit prime psuch that (p-1)/2 is prime, Magma takes only 1 second for the sieving and about 0.3 seconds to compute an individual logarithm.