63
Views
5
CrossRef citations to date
0
Altmetric
Miscellany

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

&
Pages 1481-1495 | Received 13 Dec 2002, Published online: 31 Aug 2007
 

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.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.