Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Euclid's algorithm and the
Lanczos method over finite fields

Author: Jeremy Teitelbaum
Journal: Math. Comp. 67 (1998), 1665-1678
MSC (1991): Primary 11Y16, 65F10, 15A33
MathSciNet review: 1474657
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper shows that there is a close relationship between the Euclidean algorithm for polynomials and the Lanczos method for solving sparse linear systems, especially when working over finite fields. It uses this relationship to account rigorously for the appearance of self-orthogonal vectors arising in the course of the Lanczos algorithm. It presents an improved Lanczos method which overcomes problems with self-orthogonality and compares this improved algorithm with the Euclidean algorithm.

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

  • [B] A. Bultheel, Recursive algorithms for non-normal Pade tables,, SIAM Journal on Applied Mathematics, 39, (1980), 1:106-118. MR 82e:65018
  • [C1] D. Coppersmith, Solving linear equations over $GF(2)$; block Lanczos algorithm., Linear Algebra and its Applications 192 (1993), 33-60. MR 94i:65044
  • [C2] D. Coppersmith, Solving homogeneous linear equations over $GF(2)$ via block Wiedemann algorithm, Mathematics of Computation 62 (1994), 205:333-350. MR 94c:11124
  • [D] J. L. Dornstetter, On the equivalence between Berlekamp's and Euclid's algorithms, IEEE Transactions on Information Theory 33 (1987), 3:428-431. MR 88j:94018
  • [K] E. Kaltofen, Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems, Mathematics of Computation 64 (1995), 210:777-806. MR 95f:65094
  • [M] P. Montgomery, A block Lanczos algorithm for finding dependencies over $GF(2)$, Advances in cryptology-EUROCRYPT '95 (Saint-Malo, 1995), Lecture Notes in Computer Science 921, Springer, Berlin, 1995. MR 97c:11115
  • [W] D.H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory 32 (1988), 1:54-62. MR 87g:11166

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11Y16, 65F10, 15A33

Retrieve articles in all journals with MSC (1991): 11Y16, 65F10, 15A33

Additional Information

Jeremy Teitelbaum
Affiliation: Jeremy Teitelbaum, Department of Mathematics, Statistics, and Computer Science (M/C 249), University of Illinois at Chicago, 851 S. Morgan St., Chicago, IL 60607, USA

Received by editor(s): February 8, 1996
Additional Notes: The author is supported by the National Science Foundation.
Article copyright: © Copyright 1998 American Mathematical Society

American Mathematical Society