Cryptology ePrint Archive: Report 2015/930

Nearly Sparse Linear Algebra

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

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

Date: received 23 Sep 2015

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

Available format(s): PDF | BibTeX Citation

Version: 20150927:092303 (All versions of this report)

Short URL: ia.cr/2015/930

Discussion forum: Show discussion | Start new discussion