Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)


Solving homogeneous linear equations over $ {\rm GF}(2)$ via block Wiedemann algorithm

Author: Don Coppersmith
Journal: Math. Comp. 62 (1994), 333-350
MSC: Primary 11Y16; Secondary 11-04, 15A06, 15A33
MathSciNet review: 1192970
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We propose a method of solving large sparse systems of homogeneous linear equations over $ GF(2)$, the field with two elements. We modify an algorithm due to Wiedemann. A block version of the algorithm allows us to perform 32 matrix-vector operations for the cost of one. The resulting algorithm is competitive with structured Gaussian elimination in terms of time and has much lower space requirements. It may be useful in the last stage of integer factorization.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y16, 11-04, 15A06, 15A33

Retrieve articles in all journals with MSC: 11Y16, 11-04, 15A06, 15A33

Additional Information

PII: S 0025-5718(1994)1192970-7
Article copyright: © Copyright 1994 American Mathematical Society