**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.

**Category / Keywords: **public-key cryptography / Sparse Linear Algebra. Block Wiedemann Algorithm. Discrete Logarithm. Finite Fields.

**Original Publication**** (with minor differences): **submitted to Review Volume " Contemporary Developments in Finite Fields and Applications "

**Date: **received 23 Sep 2015, last revised 7 Apr 2016

**Contact author: **Cecile Pierrot at lip6 fr, Antoine Joux at m4x org

**Available format(s): **PDF | BibTeX Citation

**Version: **20160407:174721 (All versions of this report)

**Short URL: **ia.cr/2015/930

[ Cryptology ePrint archive ]