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