Geodesic
A connection of series approximations and the basis of the Krylov space in block algorithms of Coppersmith and Montgomery
Fundamentalʹnaâ i prikladnaâ matematika, Tome 17 (2012) no. 5, pp. 211-223.

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

In this paper, some properties of the Wiedemann–Coppersmith algorithm are studied. In particular, when the matrix of a linear system is symmetric, an orthogonal basis of the Krylov space is constructed with the help of approximations of formal series from odd steps of this algorithm. We propose some modifications that use the described properties. 
@article{FPM_2012_17_5_a13,
     author = {M. A. Cherepniov},
     title = {A connection of series approximations and the basis of the {Krylov} space in block algorithms of {Coppersmith} and {Montgomery}},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {211--223},
     publisher = {mathdoc},
     volume = {17},
     number = {5},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2012_17_5_a13/}
}
TY  - JOUR
AU  - M. A. Cherepniov
TI  - A connection of series approximations and the basis of the Krylov space in block algorithms of Coppersmith and Montgomery
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2012
SP  - 211
EP  - 223
VL  - 17
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_2012_17_5_a13/
LA  - ru
ID  - FPM_2012_17_5_a13
ER  - 
%0 Journal Article
%A M. A. Cherepniov
%T A connection of series approximations and the basis of the Krylov space in block algorithms of Coppersmith and Montgomery
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2012
%P 211-223
%V 17
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_2012_17_5_a13/
%G ru
%F FPM_2012_17_5_a13
M. A. Cherepniov. A connection of series approximations and the basis of the Krylov space in block algorithms of Coppersmith and Montgomery. Fundamentalʹnaâ i prikladnaâ matematika, Tome 17 (2012) no. 5, pp. 211-223. http://geodesic.mathdoc.fr/item/FPM_2012_17_5_a13/

[1] Nesterenko Yu. V., Cherepnëv M. A. i dr., Otchët po khozdogovoru “Issledovanie algoritmicheskikh podkhodov k resheniyu sistem algebraicheskikh uravnenii nad konechnymi polyami na mnogoprotsessornykh klasterakh”, Algoritm-K, 2008

[2] Cherepnëv M. A., “Blochnyi algoritm tipa Lantsosha resheniya razrezhennykh sistem lineinykh uravnenii”, Diskret. mat., 20:1 (2008), 145–150 | DOI | MR | Zbl

[3] Astakhov V. V., “Estimates of the running time and memory requirements of the new algorithm of solving large sparse linear systems over the field with two elements”, J. Tambov State Univ., 15:4, The works of participants of Int. conf. “ParCA” presented according to the results of reviewing by International Program Committee (2010), 1311–1327 | MR

[4] Barnett M., Littlefield R., Payne D. G., van de Geijn R., “Global combine on mesh architectures with wormhole routing”, J. Parallel and Distributed Comput. Arch., 24:2 (1995), 191–201 | DOI

[5] Beckermann 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

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

[7] Giorgi P., Jeannerod C.-P., Villard G., “On complexity of polynomial matrix computations”, ISSAC' 03, Proc. of the Int. Symp. on Symbolic and Algebraic Computation (August 3–6, 2003, Philadelphia, USA), ACM, New York, 2003, 135–142 | DOI | MR | Zbl

[8] Jeannerod C.-P., Villard G., “Asymptotically fast polynomial matrix algorithms for multivariable systems”, Int. J. Control, 79:11 (2006), 1359–1367 | DOI | MR | Zbl

[9] Kaltofen E., “Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems”, Math. Comput., 64:210 (1995), 777–806 | MR | Zbl

[10] Kleinjung T., Aoki K., Franke J., Lenstra A. K., Thomé E., Bos J. W., Gaudry P., Kruppa A., Montgomery P. L., Osvik D. A., Riele H., Timofeev A., Zimmermann P., Factorization of a 768-bit RSA modulus. Version 1.0, , 2010 http://eprint.iacr.org/2010/006.pdf

[11] Montgomery P. L., “A clock Lanczos algorithm for finding dependencies over $GF(2)$”, Adv. Cryptology – EuroCrypt' 95, Lect. Notes Comput. Sci., 921, eds. L. C. Guillou, J.-J. Quisquater, Springer, Berlin, 1995, 106–120 | DOI | MR | Zbl

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

[13] Villard G., A study of Coppersmith's block Wiedemann algorithm using matrix polynomials, RR 975-I-M, IMAG, Grenoble, France, 1997