It is of interest in cryptographic applications to obtain practical performance improvements for the discrete logarithm problem
over prime fields
$
\mathbb{F}_p
$
\mathbb{F}_p
with
p of size ≤ 500 bits. The linear sieve and the cubic sieve methods described in Coppersmith, Odlyzko and Schroeppel’s paper
[
3] are two practical algorithms for computing discrete logarithms over prime fields. The cubic sieve algorithm is asymptotically
faster than the linear sieve algorithm.
We discuss an efficient implementation of the cubic sieve algorithm in- corporating two heuristic principles. We demonstrate
through empirical performance measures that for a special class of primes the cubic sieve method runs about two to three times
faster than the linear sieve method even in cases of small prime fields of size about 150 bits.