Geodesic
Implementing main steps of Wiedemann--Coppersmith algorithm for binary systems of linear equations on clusters
Prikladnaâ diskretnaâ matematika, no. 4 (2013), pp. 82-95.

Voir la notice de l'article provenant de la source Math-Net.Ru

This paper concerns implementation of the main steps of block Wiedemann's algorithm for solving systems of linear equations. Effective implementation of particular operations is provided. Specific problems of implementing the algorithm for running on clusters are studied.
Keywords: systems of linear equations, Wiedemann–Coppersmith's algorithm. 
@article{PDM_2013_4_a8,
     author = {A. S. Ryzhov},
     title = {Implementing main steps of {Wiedemann--Coppersmith} algorithm for binary systems of linear equations on clusters},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {82--95},
     publisher = {mathdoc},
     number = {4},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2013_4_a8/}
}
TY  - JOUR
AU  - A. S. Ryzhov
TI  - Implementing main steps of Wiedemann--Coppersmith algorithm for binary systems of linear equations on clusters
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2013
SP  - 82
EP  - 95
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2013_4_a8/
LA  - ru
ID  - PDM_2013_4_a8
ER  - 
%0 Journal Article
%A A. S. Ryzhov
%T Implementing main steps of Wiedemann--Coppersmith algorithm for binary systems of linear equations on clusters
%J Prikladnaâ diskretnaâ matematika
%D 2013
%P 82-95
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2013_4_a8/
%G ru
%F PDM_2013_4_a8
A. S. Ryzhov. Implementing main steps of Wiedemann--Coppersmith algorithm for binary systems of linear equations on clusters. Prikladnaâ diskretnaâ matematika, no. 4 (2013), pp. 82-95. http://geodesic.mathdoc.fr/item/PDM_2013_4_a8/

[1] Coppersmith D., “Fast evaluation of logarithms in fields of characteristic two”, IEEE Trans. Inform. Theory, IT-30:4 (1984), 587–594 | DOI | MR | Zbl

[2] Montgomery P. L., “A block Lanczos algorithm for finding dependencies over $GF(2)$”, EUROCRYPT' 95, LNCS, 921, 1995, 106–120 | MR | Zbl

[3] Coppersmith D., “Solving linear equations over $GF(2)$ via block Wiedemann algorithm”, Math. Comp., 62:205 (1994), 333–350 | MR | Zbl

[4] Kleinjung T., Aoki K., Franke J., et al., “Factorization of a 768-bit RSA modulus”, CRYPTO-2010, LNCS, 6223, 2010, 333–350 | MR | Zbl

[5] Wiedemann D. H., “Solving sparse linear equations over finite fields”, IEEE Trans. Inform. Theory, IT-32:1 (1986), 54–62 | DOI | MR | Zbl

[6] Ryzhov A. S., “O realizatsii algoritma Koppersmita dlya dvoichnykh matrichnykh posledovatelnostei na vychislitelyakh klasternogo tipa”, Prikladnaya diskretnaya matematika, 2013, no. 3, 112–122

[7] Thomé E., “Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm”, J. Symb. Comput., 33 (2002), 757–775 | DOI | MR | Zbl

[8] Akho A., Khopkroft D., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979, 536 pp. | MR

[9] Open MPI v1.6.4 documentation, , 2013 http://www.open-mpi.org/doc/v1.6

[10] Cavallar S., “Strategies for filtering in the number field sieve”, Proc. ANTS IV, LNCS, 1838, 2000, 209–231 | MR | Zbl