Reduction of Huge, Sparse Matrices over Finite Fields Via Created Catastrophes
- 1 January 1992
- journal article
- research article
- Published by Taylor & Francis in Experimental Mathematics
- Vol. 1 (2) , 89-94
- https://doi.org/10.1080/10586458.1992.10504250
Abstract
We present a heuristic method for the reduction modulo 2 of a large, sparse bit matrix to a smaller, dense bit matrix that can then be solved by conventional means, such as Gaussian elimination. This method worked effectively for us in reducing matrices as large as 100,000 × 100,000 to much smaller, but denser square matrices.Keywords
This publication has 5 references indexed in Scilit:
- Solving Large Sparse Linear Systems Over Finite FieldsPublished by Springer Nature ,2001
- Discrete logarithms in finite fields and their cryptographic significancePublished by Springer Nature ,2000
- Factoring integers with the number field sievePublished by Springer Nature ,1993
- A Pipeline Architecture for Factoring Large Integers with the Quadratic Sieve AlgorithmSIAM Journal on Computing, 1988
- Solving sparse linear equations over finite fieldsIEEE Transactions on Information Theory, 1986