On Improving Integer Factorization and Discrete Logarithm Computation using Partial Triangulation

Fabrice Boudot

Paper 2017/758

On Improving Integer Factorization and Discrete Logarithm Computation using Partial Triangulation

Fabrice Boudot

Abstract

The number field sieve is the best-known algorithm for factoring integers and solving the discrete logarithm problem in prime fields. In this paper, we present some new improvements to various steps of the number field sieve. We apply these improvements on the current 768-bit discrete logarithm record and show that we are able to perform the overall computing time in about 1260 core $\cdot$ years using these improvements instead of 2350 core $\cdot$ years using the best known parameters for this problem. Moreover, we show that the pre-computation phase for a 768-bit discrete logarithm problem, that allows for example to build a massive decryption tool of IPsec traffic protected by the Oakley group~1, was feasible in reasonable time using technologies available before the year 2000.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: RSA factoring discrete logarithm problem
Contact author(s): fabrice boudot @ orange fr
History: 2017-08-07: received
Short URL: https://ia.cr/2017/758
License: CC BY

BibTeX

@misc{cryptoeprint:2017/758,
      author = {Fabrice Boudot},
      title = {On Improving Integer Factorization and Discrete Logarithm Computation using Partial Triangulation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/758},
      year = {2017},
      url = {https://eprint.iacr.org/2017/758}
}