1
$\begingroup$

Is there any report on comparing quadratic and number field sieve performance in theory vs actual data for discrete logarithm over primes?

Is actual data better than theory in any way unexplained (I think I read this somewhere and cannot recollect)?

My query was more about distinction between theory and practice of quadratic sieve and distinction between theory and practice of number field sieve and not between distinction between quadratic and number field sieve.

$\endgroup$
2
$\begingroup$

To my knowledge, there are two reports that deal with the crossover point between the Gaussian integer sieve—which is the rough analogous of the quadratic sieve for discrete logarithms—and the number field sieve over prime fields:

  • Weber (1998) computed discrete logarithms over a 85-digit (~283 bits) prime, and concluded that at that size point the Gaussian integer sieve was faster.

  • Joux and Lercier (2003) not only compared the two algorithms, but made some improvements of their own to the number field sieve for discrete logarithms. They concluded that the number field sieve was faster already at the 100-digit (~332 bits) range.

$\endgroup$
  • $\begingroup$ thank you for the links. My query was more about distinction between theory and practice of quadratic sieve and distinction between theory and practice of number field sieve and not between distinction between quadratic and number field sieve. $\endgroup$ – Turbo Dec 4 '16 at 21:35
  • $\begingroup$ Ah. Well, the only thing I can think of, with regards to factorization, is that originally it wasn't clear whether the NFS would be practical at all, i.e., the crossover point would be too high compared to the QS. But it turned out to be quite practical, even for relatively small integers. Not sure if this is what you had in mind, though. $\endgroup$ – Samuel Neves Dec 4 '16 at 22:49
  • $\begingroup$ That is a good point in theory versus practice. Where did you find this quote? Also my query was about DLOG though. $\endgroup$ – Turbo Dec 5 '16 at 0:09
  • 1
    $\begingroup$ There is some talk of it in the introduction here. Also §8 of this. $\endgroup$ – Samuel Neves Dec 5 '16 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.