Abstract
In this paper, we report efficient implementations of the linear sieve and the cubic sieve methods for computing discrete logarithms over prime fields. We demonstrate through empirical performance measures that for a special class of primes the cubic sieve method runs about two times faster than the linear sieve method even in cases of small prime fields of the size about 150 bits. We also provide a heuristic estimate of the number of solutions of the congruence X 3 ≡ Y 2 Z (mod p) that is of central importance in the cubic sieve method.
Notes
†A preliminary version of this paper appeared in ISAAC99 Citation6.
‡We denote log x = log 10 x, ln x = log e x and lg x = log 2 x.
†More precisely, some approximate value of lg q, for example, the integer ⌊ 1000 lg q⌋.
‡The exponent h can be chosen in the sequence 1, 2, 3, … , until one finds an h for which none of the integers between −M and M is congruent to d.
§For a reason that will be clear in section 5.
¶The timings reported in ref. Citation6 are based on the Galois Field Library (GFL) Citation15 developed by the authors and were obtained on a 200 MHz Pentium processor running Linux version 2034 and having the GNU C compiler version 2.7. For this paper we opted for changing the core mathematical library, because CCRYPTO is more stable and efficient than GFL. One can readily observe that the relative performances of the two sieve methods are almost identical under both the libraries.
∥The timings reported in ref. Citation6 do not include the filtering overhead and hence are less realistic.