Available in electronic format
Available in print format		 Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

Euclid's algorithm and the Lanczos method over finite fields

Author(s): Jeremy Teitelbaum.
Journal: Math. Comp. 67 (1998), 1665-1678.
MSC (1991): Primary 11Y16, 65F10, 15A33
Retrieve article in: PDF
This article is available free of charge

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:

[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 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: 10.1090/S0025-5718-98-00973-9
PII: S 0025-5718(98)00973-9
Received by editor(s): February 8, 1996
Additional Notes: The author is supported by the National Science Foundation.
Copyright of article: Copyright 1998, American Mathematical Society

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google