Nearly Sparse Linear Algebra and application to Discrete Logarithms Computations

Antoine Joux 1 Cécile Pierrot 1
1 ALMASTY - ALgorithms for coMmunicAtion SecuriTY
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : In this article, we propose a method to perform linear algebra on a matrix with nearly sparse properties. More precisely, although we require the main part of the matrix to be sparse, we allow some dense columns with possibly large coefficients. We modify Block Wiedemann algorithm and show that the contribution of these heavy columns can be made negligible compared to the one of the sparse part of the matrix. In particular, this eases the computation of discrete logarithms in medium and high characteristic finite fields, where nearly sparse matrices naturally appear.
Type de document :
Chapitre d'ouvrage
Contemporary Developments in Finite Fields and Applications , 2016, 978-981-4719-27-8 〈10.1142/9789814719261_0008〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01154879
Contributeur : Antoine Joux <>
Soumis le : lundi 25 mai 2015 - 12:38:51
Dernière modification le : mercredi 21 mars 2018 - 18:58:20
Document(s) archivé(s) le : jeudi 20 avril 2017 - 08:12:51

Fichier

Nearly Sparse Linear Algebra.p...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Antoine Joux, Cécile Pierrot. Nearly Sparse Linear Algebra and application to Discrete Logarithms Computations. Contemporary Developments in Finite Fields and Applications , 2016, 978-981-4719-27-8 〈10.1142/9789814719261_0008〉. 〈hal-01154879〉

Partager

Métriques

Consultations de la notice

174

Téléchargements de fichiers

188