Solving large sparse linear systems over finite fields

B. A. LaMacchia, A. M. Odlyzko

Research output: Chapter in Book/Report/Conference proceedingConference contribution

106 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 languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 1990, Proceedings
EditorsAlfred J. Menezes, Scott A. Vanstone
PublisherSpringer Verlag
Pages109-133
Number of pages25
ISBN (Print)9783540545088
DOIs
StatePublished - 1991
Event10th Conference on the Theory and Application of Cryptography, CRYPTO 1990 - Santa Barbara, United States
Duration: Aug 11 1990Aug 15 1990

Publication series

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

Other

Other10th Conference on the Theory and Application of Cryptography, CRYPTO 1990
CountryUnited States
CitySanta Barbara
Period8/11/908/15/90

Fingerprint Dive into the research topics of 'Solving large sparse linear systems over finite fields'. Together they form a unique fingerprint.

  • 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