Geodesic
The universal block Lanczos–Padé method for linear systems over large prime fields
Fundamentalʹnaâ i prikladnaâ matematika, Tome 19 (2014) no. 6, pp. 225-249 
M. A. Cherepniov; N. L. Zamarashkin. The universal block Lanczos–Padé method for linear systems over large prime fields. Fundamentalʹnaâ i prikladnaâ matematika, Tome 19 (2014) no. 6, pp. 225-249. http://geodesic.mathdoc.fr/item/FPM_2014_19_6_a10/
@article{FPM_2014_19_6_a10,
     author = {M. A. Cherepniov and N. L. Zamarashkin},
     title = {The universal block {Lanczos{\textendash}Pad\'e} method for linear systems over large prime fields},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {225--249},
     year = {2014},
     volume = {19},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2014_19_6_a10/}
}
TY  - JOUR
AU  - M. A. Cherepniov
AU  - N. L. Zamarashkin
TI  - The universal block Lanczos–Padé method for linear systems over large prime fields
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2014
SP  - 225
EP  - 249
VL  - 19
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/FPM_2014_19_6_a10/
LA  - ru
ID  - FPM_2014_19_6_a10
ER  - 
%0 Journal Article
%A M. A. Cherepniov
%A N. L. Zamarashkin
%T The universal block Lanczos–Padé method for linear systems over large prime fields
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2014
%P 225-249
%V 19
%N 6
%U http://geodesic.mathdoc.fr/item/FPM_2014_19_6_a10/
%G ru
%F FPM_2014_19_6_a10

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

In this paper, we propose a universal algorithm designed for solving large sparse linear systems over finite fields with a large prime number of elements. Such systems arise in the solution of the discrete logarithm problem modulo a prime number. The algorithm has been developed for parallel computing systems with various parallel architectures and properties. The new method inherits the structural properties of the Lanczos method however providing flexible control over the complexity of parallel computations and the intensity of exchanges.

[1] Dorofeev A. Ya., “Vychislenie logarifmov v konechnom prostom pole metodom lineinogo resheta”, Tr. po diskr. matem., 5, 2002, 29–50

[2] Dorofeev A. Ya., “Reshenie sistem lineinykh uravnenii pri vychislenii logarifmov v konechnom prostom pole”, Matem. vopr. kriptogr., 3:1 (2012), 5–51

[3] Zamarashkin N. L., Algoritmy dlya razrezhennykh sistem lineinykh uravnenii v $GF(2)$, Uchebnoe posobie, Izd-vo Mosk. un-ta, M., 2013

[4] Popovyan I. A., Nesterenko Yu. V., Grechnikov E. A., Vychislitelno slozhnye zadachi teorii chisel, Uchebnoe posobie, Izd-vo Mosk. un-ta, M., 2012

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

[6] Cherepnev M. A., “Version of block Lanczos-type algorithm for solving sparse linear systems”, Bull. Math. Soc. Sci. Math. Roumanie, 53(101):3 (2010), 225–230 | MR

[7] Coppersmith D., “Solving linear equations over $GF(2)$: Block Lanczos algorithm”, Linear Algebra Appl., 193 (1993), 33–60 | DOI | MR

[8] Gutknecht M. H., “A completed theory of the unsymmetric Lanczos process and related algorithms. I”, SIAM J. Matrix Anal. Appl., 13:2 (1992), 594–639 | DOI | MR | Zbl

[9] Gutknecht M. H., “A completed theory of the unsymmetric Lanczos process and related algorithms. II”, SIAM J. Matrix Anal. Appl., 15:1 (1994), 15–58 | DOI | MR | Zbl

[10] Lanczos C., “An iteration method for the solution of the eigenvalue problem of linear differential and integral operators”, J. Res. Nat. Bur. Standards, 45 (1950), 255–282 | DOI | MR

[11] Montgomery P., “A block Lanczos algorithm for finding dependencies over $GF(2)$”, Advances in Cryptology EUROCRYPT' 95, Lect. Notes Comp. Sci., 921, Springer, Berlin, 1995, 106–120 | DOI | MR | Zbl

[12] Peterson M., Monico C., “$\mathbb F_2$ Lanczos revisited”, Linear Algebra Appl., 428 (2008), 1135–1150 | DOI | MR | Zbl