Using a grid platform for solving large sparse linear systems over GF(2)

Thorsten Kleinjung 1 Lucas Nussbaum 2 Emmanuel Thomé 3
2 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : In Fall 2009, the final step of the factorization of rsa768 was carried out on several clusters of the Grid'5000 platform, leading to a new record in integer factorization. This step involves solving a huge sparse linear system defined over the binary field GF(2). This article aims at describing the algorithm used, the difficulties encountered, and the methodology which led to success. In particular, we illustrate how our use of the block Wiedemann algorithm led to a method which is suitable for use on a grid platform, with both adaptability to various clusters, and error detection and recovery procedures. While this was not obvious at first, it eventually turned out that the contribution of the Grid'5000 clusters to this computation was major.
Type de document :
Communication dans un congrès
11th ACM/IEEE International Conference on Grid Computing (Grid 2010), Oct 2010, Brussels, Belgium. 2010, <10.1109/GRID.2010.5697952>
Liste complète des métadonnées

https://hal.inria.fr/inria-00502899
Contributeur : Lucas Nussbaum <>
Soumis le : vendredi 16 juillet 2010 - 09:34:32
Dernière modification le : vendredi 23 septembre 2016 - 01:00:40
Document(s) archivé(s) le : mardi 23 octobre 2012 - 10:31:03

Fichier

grid.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Citation

Thorsten Kleinjung, Lucas Nussbaum, Emmanuel Thomé. Using a grid platform for solving large sparse linear systems over GF(2). 11th ACM/IEEE International Conference on Grid Computing (Grid 2010), Oct 2010, Brussels, Belgium. 2010, <10.1109/GRID.2010.5697952>. <inria-00502899>

Partager

Métriques

Consultations de
la notice

465

Téléchargements du document

233