Reduction of huge, sparse matrices over finite fields via created catastrophes.(English)Zbl 0771.65023

Authors’ summary: 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\times 100,000$$ to much smaller, but denser square matrices.

MSC:

 65F30 Other matrix algorithms (MSC2010) 65F50 Computational methods for sparse matrices
Full Text:

References:

 [1] Bollobas B., Random Graphs (1985) [2] Buhler J., ”Factoring integers with the number field sieve” · Zbl 0806.11067 [3] LaMacchia B. A., Advances in Cryptology: Crypto 90 pp 109– (1991) [4] Odlyzko, A. M. ”Discrete logarithms in finite fields and their cryptographic significance”. Advances in Cryptology: Proceedings of Eurocrypt 84. Edited by: Beth, T., Cot, N. and Ingemarsson, I. pp.224–314. Berlin: Springer-Verlag. [Odlyzko 1985], Lecture Notes in Computer Science 209 [5] Pomerance C., SIAM J. Comput. 17 pp 387– (1988) · Zbl 0644.10002 [6] Wiedemann D. H., IEEE Trans. Information Theory 32 pp 54– (1986) · Zbl 0607.65015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.