Finite Fields [HB 37]

Magma V2.7 contains implementations of two index calculus methods for computing discrete logarithms in prime finite fields: the linear sieve and the Gaussian integer sieve.

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 p such that (p-1)/2 is prime, Magma takes only 1 second for the sieving and about 0.3 seconds to compute an individual logarithm.

New features:

• The arithmetic for extension fields of moderate to large prime fields has been improved.
• Index calculus method using either the Gaussian integer sieve or linear sieve (for prime fields $\mbox{\rm GF}(p)$).