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

DOI:
https://doi.org/10.1090/S0025-5718-98-00973-9

MathSciNet review:
1474657

Full-text PDF Free Access

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.

**[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 ; block Lanczos algorithm.*, Linear Algebra and its Applications**192**(1993), 33-60. MR**94i:65044****[C2]**D. Coppersmith,*Solving homogeneous linear equations over 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*, 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**

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

Email:
jeremy@uic.edu

DOI:
https://doi.org/10.1090/S0025-5718-98-00973-9

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