We present new baby steps/giant steps algorithms of asymptotically fast running time for
dense matrix problems. Our algorithms compute the determinant, characteristic polynomial …

We study the link between the complexity of polynomial matrix multiplication and the
complexity of solving other basic linear algebra problems on polynomial matrices. By …

We give complexity estimates for the problems of evaluation and interpolation on various
polynomial bases. We focus on the particular cases when the sample points form an …

This paper describes a new algorithm for computing linear generators (vector generating
polynomials) for matrix sequences, running in subquadratic time. This algorithm applies in …

Turbo-code encoders are one of the spreadest family of error correcting codes used in the
communication's world, especially in space transmissions. This paper presents an efficient …

We describe in this article how we have been able to extend the record for computations of
discrete logarithm sin characteristic 2 from the previous record over F _ 2^ 503 to a newer …

In this thesis, we study algorithms for a problem of finding relations in one or several
variables. It generalizes that of computing a solution to a system of linear modular equations …

arXiv:1204.3735v1 [cs.SC] 17 Apr 2012 Page 1 Computational linear algebra over finite fields
Jean-Guillaume Dumas∗ Clément Pernet† April 18, 2012 1 Dense matrix multiplication 2 1.1 …

The security of most current public-key cryptosystems is based on the difficulty of finding
discrete logarithms in large finite fields or factoring large integers. Most discrete logarithm …

Le calcul de logarithmes discrets est un problème central en cryptologie. Lorsqu'un
algorithme sous-exponentiel pour résoudre ce problème existe, le cryptosystème concerné …