Integer factorization and discrete logarithm problems
Résumé
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.
Domaines
Cryptographie et sécurité [cs.CR]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...