The filtering step of discrete logarithm and integer factorization algorithms

Preprint English OPEN
Bouvier , Cyril;
  • Publisher: HAL CCSD
  • Subject: [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] | Number Field Sieve | discrete logarithm | Function Field Sieve | [ INFO.INFO-CR ] Computer Science [cs]/Cryptography and Security [cs.CR] | Function Field Sieve. | factorization | filtering | linear algebra | sparse linear system | structured Gaussian elimination

The security of most current public-key cryptosystems is based on the difficulty of finding discrete logarithms in large finite fields or factoring large integers. Most discrete logarithm and integer factoring algorithms, such as the Number Field Sieve (NFS) or the Func... View more
  • References (19)
    19 references, page 1 of 2

    [1] B. LaMacchia, A. Odlyzko, Solving large sparse linear systems over finite fields, in: A. Menezes, S. Vanstone (Eds.), Advances in CryptologyCRYPT0' 90, Vol. 537 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 1991, pp. 109-133.

    [2] C. Pomerance, J. W. Smith, Reduction of huge, sparse matrices over finite fields via created catastrophes, in: Experimental Mathematics, Vol. 1, 1992, pp. 89-94.

    [3] S. Cavallar, On the number field sieve integer factorization algorithm, Ph.D. thesis, Universiteit Leiden (2002).

    [4] S. Bai, P. Gaudry, A. Kruppa, F. Morain, E. Thomé, P. Zimmermann, Crible algébrique: distribution, optimisation (CADO-NFS), http: //

    [5] J. Papadopoulos, Msieve,

    [6] C. Monico, GGNFS, ggnfs.

    [7] A. Lenstra, H. Lenstra, M. Manasse, J. Pollard, The number field sieve, in: A. Lenstra, H. Lenstra (Eds.), The development of the number field sieve, Vol. 1554 of Lecture Notes in Mathematics, Springer Berlin / Heidelberg, 1993.

    [8] L. M. Adleman, The function field sieve, in: L. M. Adleman, M.-D. Huang (Eds.), Algorithmic Number Theory, Vol. 877 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 1994, pp. 108-121.

    [9] T. Kleinjung, K. Aoki, J. Franke, A. K. Lenstra, E. Thomé, J. W. Bos, P. Gaudry, A. Kruppa, P. L. Montgomery, D. A. Osvik, H. T. Riele, A. Timofeev, P. Zimmermann, Factorization of a 768-bit RSA modulus, in: T. Rabin (Ed.), CRYPTO 2010, Vol. 6223 of Lecture Notes in Computer Science, Springer Verlag, Santa Barbara, USA, 2010, pp. 333-350.

    [10] R. Barbulescu, C. Bouvier, J. Detrey, P. Gaudry, H. Jeljeli, E. Thomé, M. Videau, P. Zimmermann, Discrete logarithm in GF(2809) with FFS, preprint, 6 pages, available at (2013).

  • Related Research Results (1)
  • Metrics
Share - Bookmark