The filtering step of discrete logarithm and integer factorization algorithms

Cyril Bouvier 1
1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : 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 Function Field Sieve (FFS), can be described in 3 main steps: data collection, filtering and linear algebra. The goal of the filtering step is to generate a small, sparse matrix over a finite field, for which one will compute the kernel during the linear algebra step. The filtering step is mainly a structured Gaussian elimination (SGE). For the current factorization records, billions of data are collected in the first step and have to be processed in the filtering step. One part of the filtering step is to remove heavy rows of the matrix. The choice of the weight function to select heavy rows is critical in order to obtain the smallest matrix possible. In this paper, several weight functions are studied in order to determine which one is more suited in the context of discrete logarithm and factorization algorithms.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-00734654
Contributor : Cyril Bouvier <>
Submitted on : Monday, June 3, 2013 - 12:44:18 PM
Last modification on : Thursday, July 25, 2019 - 9:56:01 AM
Long-term archiving on : Tuesday, April 4, 2017 - 3:30:17 PM

File

article.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00734654, version 3

Collections

Citation

Cyril Bouvier. The filtering step of discrete logarithm and integer factorization algorithms. 2013. ⟨hal-00734654v3⟩

Share

Metrics

Record views

942

Files downloads

776