Solving large sparse linear systems over finite fields

B. A. LaMacchia; A. M. Odlyzko

doi:10.1007/3-540-38424-3_8

Solving large sparse linear systems over finite fields

B. A. LaMacchia, A. M. Odlyzko

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

118 Scopus citations

Abstract

Many of the fast methods for factoring integers and computing discrete logarithms require the solution of large sparse linear systems of equations over finite fields. This paper presents the results of implementations of several linear algebra algorithms. It shows that very large sparse systems can be solved efficiently by using combinations of structured Gaussian elimination and the conjugate gradient, Lanczos, and Wiedemann methods.

Original language	English (US)
Title of host publication	Advances in Cryptology – CRYPTO 1990, Proceedings
Editors	Alfred J. Menezes, Scott A. Vanstone
Publisher	Springer Verlag
Pages	109-133
Number of pages	25
ISBN (Print)	9783540545088
DOIs	https://doi.org/10.1007/3-540-38424-3_8
State	Published - 1991
Event	10th Conference on the Theory and Application of Cryptography, CRYPTO 1990 - Santa Barbara, United States Duration: Aug 11 1990 → Aug 15 1990

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	537 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	10th Conference on the Theory and Application of Cryptography, CRYPTO 1990
Country/Territory	United States
City	Santa Barbara
Period	8/11/90 → 8/15/90

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1991.

Publisher link

10.1007/3-540-38424-3_8

Find It

Find It at U of M Libraries

Cite this

LaMacchia, B. A., & Odlyzko, A. M. (1991). Solving large sparse linear systems over finite fields. In A. J. Menezes, & S. A. Vanstone (Eds.), Advances in Cryptology – CRYPTO 1990, Proceedings (pp. 109-133). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 537 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-38424-3_8

Solving large sparse linear systems over finite fields. / LaMacchia, B. A.; Odlyzko, A. M.
Advances in Cryptology – CRYPTO 1990, Proceedings. ed. / Alfred J. Menezes; Scott A. Vanstone. Springer Verlag, 1991. p. 109-133 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 537 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

LaMacchia, BA & Odlyzko, AM 1991, Solving large sparse linear systems over finite fields. in AJ Menezes & SA Vanstone (eds), Advances in Cryptology – CRYPTO 1990, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 537 LNCS, Springer Verlag, pp. 109-133, 10th Conference on the Theory and Application of Cryptography, CRYPTO 1990, Santa Barbara, United States, 8/11/90. https://doi.org/10.1007/3-540-38424-3_8

LaMacchia BA, Odlyzko AM. Solving large sparse linear systems over finite fields. In Menezes AJ, Vanstone SA, editors, Advances in Cryptology – CRYPTO 1990, Proceedings. Springer Verlag. 1991. p. 109-133. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-38424-3_8

@inproceedings{0dff1bb93e3c428a9b9c4ccb177bc565,

title = "Solving large sparse linear systems over finite fields",

abstract = "Many of the fast methods for factoring integers and computing discrete logarithms require the solution of large sparse linear systems of equations over finite fields. This paper presents the results of implementations of several linear algebra algorithms. It shows that very large sparse systems can be solved efficiently by using combinations of structured Gaussian elimination and the conjugate gradient, Lanczos, and Wiedemann methods.",

author = "LaMacchia, {B. A.} and Odlyzko, {A. M.}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1991.; 10th Conference on the Theory and Application of Cryptography, CRYPTO 1990 ; Conference date: 11-08-1990 Through 15-08-1990",

year = "1991",

doi = "10.1007/3-540-38424-3_8",

language = "English (US)",

isbn = "9783540545088",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "109--133",

editor = "Menezes, {Alfred J.} and Vanstone, {Scott A.}",

booktitle = "Advances in Cryptology – CRYPTO 1990, Proceedings",

}

TY - GEN

T1 - Solving large sparse linear systems over finite fields

AU - LaMacchia, B. A.

AU - Odlyzko, A. M.

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1991.

PY - 1991

Y1 - 1991

N2 - Many of the fast methods for factoring integers and computing discrete logarithms require the solution of large sparse linear systems of equations over finite fields. This paper presents the results of implementations of several linear algebra algorithms. It shows that very large sparse systems can be solved efficiently by using combinations of structured Gaussian elimination and the conjugate gradient, Lanczos, and Wiedemann methods.

AB - Many of the fast methods for factoring integers and computing discrete logarithms require the solution of large sparse linear systems of equations over finite fields. This paper presents the results of implementations of several linear algebra algorithms. It shows that very large sparse systems can be solved efficiently by using combinations of structured Gaussian elimination and the conjugate gradient, Lanczos, and Wiedemann methods.

UR - http://www.scopus.com/inward/record.url?scp=84988216913&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84988216913&partnerID=8YFLogxK

U2 - 10.1007/3-540-38424-3_8

DO - 10.1007/3-540-38424-3_8

M3 - Conference contribution

AN - SCOPUS:84988216913

SN - 9783540545088

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 109

EP - 133

BT - Advances in Cryptology – CRYPTO 1990, Proceedings

A2 - Menezes, Alfred J.

A2 - Vanstone, Scott A.

PB - Springer Verlag

T2 - 10th Conference on the Theory and Application of Cryptography, CRYPTO 1990

Y2 - 11 August 1990 through 15 August 1990

ER -

Solving large sparse linear systems over finite fields

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this