Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm

Abstract : This paper describes a new algorithm for computing linear generators (vector generating polynomials) for matrix sequences, running in sub-quadratic time. This algorithm applies in particular to the sequential stage of Coppersmith's block Wiedemann algorithm. Experiments showed that our method can be substituted in place of the quadratic one proposed by Coppersmith, yielding important speedups even for realistic matrix sizes. The base fields we were interested in were finite fields of large characteristic. As an example, we have been able to compute a linear generator for a sequence of 4*4 matrices of length 242 304 defined over GF(2^607) in less than two days on one 667MHz alpha ev67 cpu.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2002, 33 (5), pp.757-775. 〈10.1006/jsco.2002.0533〉
Liste complète des métadonnées

Littérature citée [32 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00103417
Contributeur : Emmanuel Thomé <>
Soumis le : mercredi 4 octobre 2006 - 12:47:02
Dernière modification le : jeudi 10 mai 2018 - 02:06:15
Document(s) archivé(s) le : mardi 6 avril 2010 - 18:04:25

Fichier

Identifiants

Collections

Citation

Emmanuel Thomé. Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm. Journal of Symbolic Computation, Elsevier, 2002, 33 (5), pp.757-775. 〈10.1006/jsco.2002.0533〉. 〈inria-00103417〉

Partager

Métriques

Consultations de la notice

235

Téléchargements de fichiers

556