Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Solving homogeneous linear equations over $\textrm {GF}(2)$ via block Wiedemann algorithm
HTML articles powered by AMS MathViewer

by Don Coppersmith PDF
Math. Comp. 62 (1994), 333-350 Request permission

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
    E. Cahen, Théorie des nombres. I, Hermann, Paris, 1914, pp. 336-338. D. Coppersmith, Solving linear equations over $GF(2)$, IBM Research Rep. RC 16997, July 1, 1991.
  • Jean-Louis Dornstetter, On the equivalence between Berlekamp’s and Euclid’s algorithms, IEEE Trans. Inform. Theory 33 (1987), no. 3, 428–431. MR 885401, DOI 10.1109/TIT.1987.1057299
  • Fred G. Gustavson and David Y. Y. Yun, Fast algorithms for rational Hermite approximation and solution of Toeplitz systems, IEEE Trans. Circuits and Systems 26 (1979), no. 9, 750–755. MR 549385, DOI 10.1109/TCS.1979.1084696
  • Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
  • Erich Kaltofen and B. David Saunders, On Wiedemann’s method of solving sparse linear systems, Applied algebra, algebraic algorithms and error-correcting codes (New Orleans, LA, 1991) Lecture Notes in Comput. Sci., vol. 539, Springer, Berlin, 1991, pp. 29–38. MR 1229306, DOI 10.1007/3-540-54522-0_{9}3
    • B. A. LaMacchia and A. M. Odlyzko, Solving large sparse linear systems over finite fields, Advances in Cryptology—CRYPTO ’90 (A. J. Menezes and S. A. Vanstone, eds.), vol. 537, Springer-Verlag, Berlin and New York, 1991, pp. 109-133.
  • J. A. Reeds and N. J. A. Sloane, Shift-register synthesis (modulo $m$), SIAM J. Comput. 14 (1985), no. 3, 505–513. MR 795927, DOI 10.1137/0214038
  • Douglas H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), no. 1, 54–62. MR 831560, DOI 10.1109/TIT.1986.1057137
Similar Articles
Additional Information
  • © Copyright 1994 American Mathematical Society
  • Journal: Math. Comp. 62 (1994), 333-350
  • MSC: Primary 11Y16; Secondary 11-04, 15A06, 15A33
  • DOI: https://doi.org/10.1090/S0025-5718-1994-1192970-7
  • MathSciNet review: 1192970