Geodesic
Implementing Coppersmith algorithm for binary matrix sequences on clusters
Prikladnaâ diskretnaâ matematika, no. 3 (2013), pp. 112-122
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2013},
     number = {3},
     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
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
%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