Integer factorization and discrete logarithm problems

Pierrick Gaudry 1
1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : These are notes for a lecture given at CIRM in 2014, for the Journées Nationales du Calcul Formel. We explain the basic algorithms based on combining congruences for solving the integer factorization and the discrete logarithm problems. We highlight two particular situations where the interaction with symbolic computation is visible: the use of Gröbner basis in Joux's algorithm for discrete logarithm in nite eld of small characteristic, and the exact sparse linear algebra tools that occur in the Number Field Sieve algorithm for discrete logarithm in large characteristic.
Document type :
Preprints, Working Papers, ...
Liste complète des métadonnées

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/hal-01215553
Contributor : Pierrick Gaudry <>
Submitted on : Wednesday, October 14, 2015 - 2:42:44 PM
Last modification on : Tuesday, December 18, 2018 - 4:18:25 PM
Document(s) archivé(s) le : Thursday, April 27, 2017 - 4:23:46 AM

File

poly.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01215553, version 1

Collections

Citation

Pierrick Gaudry. Integer factorization and discrete logarithm problems. 2014. ⟨hal-01215553⟩

Share

Metrics

Record views

402

Files downloads

1567