Solving homogeneous linear equations over via block Wiedemann algorithm

Author:
Don Coppersmith

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

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We propose a method of solving large sparse systems of homogeneous linear equations over , 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.

**[1]**E. Cahen,*Théorie des nombres*. I, Hermann, Paris, 1914, pp. 336-338.**[2]**D. Coppersmith,*Solving linear equations over*, IBM Research Rep. RC 16997, July 1, 1991.**[3]**J. L. Dornstetter,*On the equivalence between Berlekamp's and Euclid's algorithms*, IEEE Trans. Inform. Theory**33**(1987), 428-431. MR**885401 (88j:94018)****[4]**F. G. Gustavson and D. Y. Y. Yun,*Fast algorithms for rational Hermite approximation and solution of Toeplitz systems*, IEEE Trans. Circuits and Systems**26**(1979), 750-755. MR**549385 (80h:68040)****[5]**D. E. Knuth,*The art of computer programming*. Vol. 2:*Seminumerical algorithms*, 2nd ed., Addison-Wesley, Reading, MA, 1981, exercise 4.6.1.19, pp. 419, 621. MR**633878 (83i:68003)****[6]**E. Kaltofen and B. D. Saunders,*On Wiedemann's method of solving sparse linear systems*, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (H. F. Mattson, T. Mora, and T. R. N. Rao, eds.), Lecture Notes in Comput. Sci., vol. 539, Springer-Verlag, Berlin and New York, 1991, pp. 29-38. MR**1229306****[7]**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.**[8]**J. A. Reeds and N. J. A. Sloane,*Shift-register synthesis*(*modulo m*), SIAM J. Comput.**14**(1985), 505-513. MR**795927 (86i:94068)****[9]**D. H. Wiedemann,*Solving sparse linear equations over finite fields*, IEEE Trans. Inform. Theory**32**(1986), 54-62. MR**831560 (87g:11166)**

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

DOI:
https://doi.org/10.1090/S0025-5718-1994-1192970-7

Article copyright:
© Copyright 1994
American Mathematical Society