Paper 2015/930

Nearly Sparse Linear Algebra and application to Discrete Logarithms Computations

Antoine Joux and Cécile Pierrot

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. submitted to Review Volume " Contemporary Developments in Finite Fields and Applications "
Keywords
Sparse Linear AlgebraBlock Wiedemann AlgorithmDiscrete LogarithmFinite Fields.
Contact author(s)
Cecile Pierrot @ lip6 fr
Antoine Joux @ m4x org
History
2016-04-07: last of 2 revisions
2015-09-27: received
See all versions
Short URL
https://ia.cr/2015/930
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/930,
      author = {Antoine Joux and Cécile Pierrot},
      title = {Nearly Sparse Linear Algebra and application to Discrete Logarithms Computations},
      howpublished = {Cryptology ePrint Archive, Paper 2015/930},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/930}},
      url = {https://eprint.iacr.org/2015/930}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.