Solving systems of linear equations arising in the computation of logarithms in a finite prime field

A. Ya. Dorofeev

Matematičeskie voprosy kriptografii, Tome 3 (2012) no. 1, pp. 5-51

Résumé

Empirical investigations of the computational complexity of algorithms for solving sparse linear systems was conducted for systems appeared in the computation of discrete logarithms in finite prime fields $GF(p)$, $p10^{135}$.

Bibliographie

[1] Diffie W., Hellman M. E., “New directions in cryptography”, IEEE Trans. Inform. Theory, 22:6 (1976), 644–654 | DOI | MR | Zbl

[2] Odlyzko A. M., “Discrete logarithms: the past and future”, Designs, Codes and Cryptography, 19:2 (2000), 129–145 | DOI | MR | Zbl

[3] LaMacchia B. A., Odlyzko A. M., “Computation of discrete logarithms in prime fields”, Designs, Codes and Cryptography, 1:1 (1991), 47–62 | DOI | MR | Zbl

[4] Weber D., On the computation of discrete logarithms in finite prime fields, Ph. D. Thesis, Univ. des Saarlandes, 1997, 111 pp.

[5] Denny T. F., Lösen großer dünnbesetztr Gleichungssysteme uber endlichen Primkörpern, Ph. D. Thesis, Univ. des Saarlandes, 1997, 137 pp.

[6] Joux A., Lercier R., “Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method”, Mathematics of Computation, 72:242 (2003), 953–967 | DOI | MR | Zbl

[7] Joux A., Lercier R., Discrete logarithms in $GF(p)$, 19.01.2001 http://listserv.nodak.edu/archives/nmbrthry.html

[8] Joux A., Lercier R., Discrete logarithms in $GF(p)$, 17.04.2001 http://listserv.nodak.edu/archives/nmbrthry.html

[9] Joux A., Lercier R., Discrete logarithms in $GF(p)$ – 130 digits, 18.06.2005 http://listserv.nodak.edu/archives/nmbrthry.html

[10] Dorofeev A. Ya., Dygin D. M., Matyukhin D. V., “Discrete logarithms in $GF(p)$ – 135 digits”, International Scientific Conference “Diophante and analytic problems in number theory” dedicated to the 100th birthday of A. O. Gelfond, Abstracts, Moscow, 2007, 14–15; 22.12.2006 http://listserv.nodak.edu/archives/nmbrthry.html

[11] Kleinjung T., Discrete logarithms in $GF(p)$ – 160 digits, 05.02.2007 http://listserv.nodak.edu/archives/nmbrthry.html

[12] Lanczos C., “Solutions of systems of linear equations by minimized iterations”, J. Res. Nat. Bureu of Standards, 49 (1952), 33–53 | MR

[13] Wiedemann D. H., “Solving sparse linear equations over finite fields”, IEEE Trans. Inform. Theory, 32:4 (1986), 354–375 | MR

[14] LaMacchia B. A., Odlyzko A. M., “Solving large sparse linear systems over finite fields”, Lecture Notes in Computer Science, 537, 1991, 109–133 | DOI | Zbl

[15] Lambert R., Computational aspects of discrete logarithms, Ph. D. Thesis, University of Waterloo, Ontario, 1996, 113 pp. | Zbl

[16] Odlyzko A. M., “Discrete logarithms in finite fields and their cryptographic significance”, Lecture Notes in Computer Sciences, 209, 1984, 224–316 | DOI | MR

[17] Coppersmith D., Odlyzko A. M., Schroepel R., “Discrete logarithms in $GF(p)$”, Algorithmica, 1:1 (1986), 1–15 | DOI | MR | Zbl

[18] Matyukhin D. V., “Ob asimptoticheskoi slozhnosti diskretnogo logarifmirovaniya v pole $GF(p)$”, Diskretnaya matematika, 15:1 (2003), 28–49 | MR | Zbl

[19] Vasilenko O. N., Teoretiko-chislovye algoritmy v kriptografii, MTsNMO, M., 2003, 325 pp. | MR

[20] Pohlig S., Hellman M., “An improved algorithm for computing logarithms over $GF(p)$ and its cryptographic significance”, IEEE Trans. Inform. Theory, 24 (1978), 106–110 | DOI | MR | Zbl

[21] Gordon D. M., “Discrete logarithms in $GF(p)$ using the number field sieve”, SIAM J. Discr. Math., 6:1 (1993), 124–138 | DOI | MR | Zbl

[22] Semaev I., “Special prime numbers and discrete logs in prime finite fields”, Mathematics of Computation, 71:237 (2002), 363–377 | DOI | MR | Zbl

[23] Gantmakher F. R., Teoriya matrits, M., 1988, 491 pp. | MR | Zbl

[24] Dorofeev A. Ya., “Vychislenie logarifmov v konechnom prostom pole metodom lineinogo resheta”, Trudy po diskretnoi matematike, 5, 2002, 29–50

[25] Eberly W., Kaltofen E., “On randomized Lanczos algorithms”, Proc. Internat. Symp. Symbolic Algebraic Comput., ISSAC' 97, N.Y., 1997, 176–183 | DOI | MR | Zbl

[26] Tyuarson R., Razrezhennye matritsy, Mir, M., 1977, 189 pp. | MR

[27] Knut D. E., Iskusstvo programmirovaniya, v. 2, Poluchislennye algoritmy, Vilyams, M., 2000, 828 pp.

[28] Barret R. et al., Templates for the solution of linear systems: building blocks for iterative methods, SIAM, Philadelphia, 1994, 107 pp. | MR | Zbl

[29] Duff I. S., van der Vorst H. A., “Developments and trends in the parallel solution of linear systems”, Parallel Computing, 25 (1999), 1931–1970 | DOI | MR

[30] Markowitz H. M., “The elimination form of the inverse and its application to linear programming”, Management Sci., 3 (1957), 255–269 | DOI | MR | Zbl

[31] Knut D. E., Iskusstvo programmirovaniya, v. 3, Sortirovka i poisk, Vilyams, M., 2000, 822 pp.

[32] Dehn T., Eiermann M., Giebermann K., Sperling V., “Structured sparse matrix-vector multiplication on massively parallel SIMD architectures”, Parallel Computing, 21 (1995), 1867–1894 | DOI | MR

[33] McLay R. T., Swift S., Carey G. F., “Maximizing sparse matrix-vector performance on RISC based MIMD computers”, Journal of Parallel and Distributed Computing, 37 (1996), 146–158 | DOI

[34] Ujaldon M., Zapata E. L., Sharma S. D., Saltz J., “Parallelization techniques for sparse matrix applications”, Journal of Parallel and Distributed Computing, 38 (1996), 256–266 | DOI

[35] Colombet L., Michallon P., Trystram D., “Parallel matrix-vector product on rings with a minimum of communications”, Parallel Computing, 22 (1996), 289–310 | DOI | MR | Zbl

[36] Basermann A., “Conjugate gradient and Lanczos methods for sparse matrices on distributed memory multiprocessor”, Journal of Parallel and Distributed Computing, 45 (1997), 46–52 | DOI | Zbl

[37] Nastea A. G., Frieder O., El-Ghazawi T., “Load-balanced sparse matrix-vector multiplication on parallel computers”, Journal of Parallel and Distributed Computing, 46 (1997), 180–193 | DOI

[38] Basermann A., Reichel B., Schelthoff C., “Preconditioned CG methods for sparse matrices on massively parallel machines”, Parallel Computing, 23 (1997), 381–398 | DOI | MR | Zbl

[39] Ghose D., Kim H. J., “Load partitioning and trade-off study for large matrix-vector computations in multicast bus networks with communication delays”, Journal of Parallel and Distributed Computing, 55 (1998), 32–59 | DOI | Zbl

[40] Geus R., Rollin S., “Towards a fast parallel spase symmetric matrix-vector multiplication”, Parallel Computing, 27 (2001), 883–896 | DOI | Zbl

[41] Gropp W., Lusk E., Skjellum A., Using MPI. Portable Parallel Programming with the Message-Passing Interface, MIT Press, 1999, 371 pp.

[42] Korneev V. D., Parallelnoe programmirovanie v MPI, M., 2003, 303 pp.

[43] Voevodin V. V., Voevodin V. V., Parallelnye vychisleniya, SPb., 2004, 608 pp.

[44] Zabrodin A. V., Levin V. K., “Opyt razrabotki parallelnykh vychislitelnykh tekhnologii. Sozdanie i razvitie semeistva MVS”, Trudy Vserossiiskoi nauchnoi konferentsii “Vysokoproizvoditelnye sistemy i ikh prilozheniya”, M., 2000, 3–8

[45] Dorofeev A. Ya., “Reshenie razrezhennykh sistem lineinykh uravnenii pri vychislenii logarifmov v konechnom prostom pole”, Materialy shestoi konferentsii “Matematika i bezopasnost informatsionnykh tekhnologii” (MaBIT–2007), M., 2008, 121–128