Euclid’s algorithm and the Lanczos method over finite fields

Teitelbaum, Jeremy

doi:10.1090/S0025-5718-98-00973-9

Euclid’s algorithm and the Lanczos method over finite fields
HTML articles powered by AMS MathViewer

by Jeremy Teitelbaum PDF

Math. Comp. 67 (1998), 1665-1678 Request permission

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

A. Bultheel and L. Wuytack, Stability of numerical methods for computing Padé approximants, Approximation theory, III (Proc. Conf., Univ. Texas, Austin, Tex., 1980), Academic Press, New York-London, 1980, pp. 267–272. MR 602726
Don Coppersmith, Solving linear equations over $\textrm {GF}(2)$: block Lanczos algorithm, Linear Algebra Appl. 192 (1993), 33–60. Computational linear algebra in algebraic and related problems (Essen, 1992). MR 1236735, DOI 10.1016/0024-3795(93)90235-G
Don Coppersmith, Solving homogeneous linear equations over $\textrm {GF}(2)$ via block Wiedemann algorithm, Math. Comp. 62 (1994), no. 205, 333–350. MR 1192970, DOI 10.1090/S0025-5718-1994-1192970-7
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
Erich Kaltofen, Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems, Math. Comp. 64 (1995), no. 210, 777–806. MR 1270621, DOI 10.1090/S0025-5718-1995-1270621-1
Peter L. Montgomery, A block Lanczos algorithm for finding dependencies over $\textrm {GF}(2)$, Advances in cryptology—EUROCRYPT ’95 (Saint-Malo, 1995) Lecture Notes in Comput. Sci., vol. 921, Springer, Berlin, 1995, pp. 106–120. MR 1367513, DOI 10.1007/3-540-49264-X_{9}
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