Geodesic
Implementing Coppersmith algorithm for binary matrix sequences on clusters
Prikladnaâ diskretnaâ matematika, no. 3 (2013), pp. 112-122.

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

This paper concerns implementation of Coppersmith algorithm, which allows to calculate vector generating polynomials. Data representation for binary matrix sequences is considered. Effective parallelization for multicore CPUs and clusters provided.
Mots-clés : matrix sequences
Keywords: Coppersmith algorithm. 
@article{PDM_2013_3_a11,
     author = {A. S. Ryzhov},
     title = {Implementing {Coppersmith} algorithm for binary matrix sequences on clusters},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {112--122},
     publisher = {mathdoc},
     number = {3},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2013_3_a11/}
}
TY  - JOUR
AU  - A. S. Ryzhov
TI  - Implementing Coppersmith algorithm for binary matrix sequences on clusters
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2013
SP  - 112
EP  - 122
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2013_3_a11/
LA  - ru
ID  - PDM_2013_3_a11
ER  - 
%0 Journal Article
%A A. S. Ryzhov
%T Implementing Coppersmith algorithm for binary matrix sequences on clusters
%J Prikladnaâ diskretnaâ matematika
%D 2013
%P 112-122
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2013_3_a11/
%G ru
%F PDM_2013_3_a11
A. S. Ryzhov. Implementing Coppersmith algorithm for binary matrix sequences on clusters. Prikladnaâ diskretnaâ matematika, no. 3 (2013), pp. 112-122. http://geodesic.mathdoc.fr/item/PDM_2013_3_a11/

[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 $\mathrm{GF}(2)$”, EUROCRYPT' 95, LNCS, 921, 1995, 106–120 | MR | Zbl

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

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

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

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

[7] Beckerman B., Labahn G., “A uniform approach for the fast computation of matrix-type Padé approximants”, SIAM J. Matrix Anal. Appl., 15:3 (1994), 804–823 | DOI | MR | Zbl