On the cubic sieve method for computing discrete logarithms over prime fields

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 ³ ≡ Y ² Z (mod p) that is of central importance in the cubic sieve method.

Keywords:

• Cryptography
• Cryptanalysis
• Finite field
• Discrete logarithm
• Sieve method

Notes

^†A preliminary version of this paper appeared in ISAAC99 6.

^‡We denote log x = log ₁₀ x, ln x = log _e x and lg x = log ₂ 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. 6 are based on the Galois Field Library (GFL) 15 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. 6 do not include the filtering overhead and hence are less realistic.