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. This is achieved by modifying the Block Wiedemann algorithm. Under some precisely stated conditions on the choices of initial vectors in the algorithm, we show that our variation not only produces a random solution of a linear system but gives a full basis of the set of solutions. Moreover, when the number of heavy columns is small, the cost of dealing with them becomes negligible. In particular, this eases the computation of discrete logarithms in medium and high characteristic finite fields, where nearly sparse matrices naturally occur.
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

https://hal.inria.fr/hal-01154879
Contributeur : Antoine Joux <>
Soumis le : samedi 25 août 2018 - 11:57:40
Dernière modification le : vendredi 31 août 2018 - 09:25:58

Fichier

JouxAntoine-v25mars-HAL.pdf
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-01154879v2〉

Partager

Métriques

Consultations de la notice

26

Téléchargements de fichiers

27