### 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 | |

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 | United States |

City | Santa Barbara |

Period | 8/11/90 → 8/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