CurrentUnless stated otherwise, the seminar takes place on Tuesdays, from 10 to 11, in room 385 at IMB. To get announcements, you can subscribe to the mailing-list.
- 2017-03-1410:00Salle 385Cécile Pierrot (Centrum Wiskunde & Informatica, Amsterdam)Nearly sparse linear algebraLinear algebra is a widely used tool both in mathematics and computer science, and cryptography is no exception to this rule. Yet, it introduces some particularities, such as dealing with linear systems that are often sparse, or, in other words, linear systems inside which a lot of coefficients are equal to zero. We propose to enlarge this notion to nearly sparse matrices, characterized by the concatenation of a sparse matrix and some dense columns, and to design an algorithm to solve this kind of problems. Motivated by discrete logarithms computations on medium and high characteristic finite fields, the Nearly Sparse Linear Algebra bridges the gap between classical dense linear algebra problems and sparse linear algebra ones, for which specific methods have already been established. Our algorithm particularly applies on one of the three phases of NFS (Number Field Sieve) which precisely consists in finding a non trivial element of the kernel of a nearly sparse matrix.
This is a joint work with Antoine Joux.