{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T06:18:58Z","timestamp":1776838738759,"version":"3.51.2"},"reference-count":7,"publisher":"American Mathematical Society (AMS)","issue":"224","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>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.<\/p>","DOI":"10.1090\/s0025-5718-98-00973-9","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:14:44Z","timestamp":1027707284000},"page":"1665-1678","source":"Crossref","is-referenced-by-count":9,"title":["Euclid\u2019s algorithm and the Lanczos method over finite fields"],"prefix":"10.1090","volume":"67","author":[{"given":"Jeremy","family":"Teitelbaum","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1998]]},"reference":[{"key":"1","isbn-type":"print","first-page":"267","article-title":"Stability of numerical methods for computing Pad\u00e9 approximants","author":"Bultheel, A.","year":"1980","ISBN":"https:\/\/id.crossref.org\/isbn\/0121710505"},{"key":"2","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0024-3795(93)90235-G","article-title":"Solving linear equations over \ud835\udc3a\ud835\udc39(2): block Lanczos algorithm","volume":"192","author":"Coppersmith, Don","year":"1993","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"205","key":"3","doi-asserted-by":"publisher","first-page":"333","DOI":"10.2307\/2153413","article-title":"Solving homogeneous linear equations over \ud835\udc3a\ud835\udc39(2) via block Wiedemann algorithm","volume":"62","author":"Coppersmith, Don","year":"1994","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"3","key":"4","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1109\/TIT.1987.1057299","article-title":"On the equivalence between Berlekamp\u2019s and Euclid\u2019s algorithms","volume":"33","author":"Dornstetter, Jean-Louis","year":"1987","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"210","key":"5","doi-asserted-by":"publisher","first-page":"777","DOI":"10.2307\/2153451","article-title":"Analysis of Coppersmith\u2019s block Wiedemann algorithm for the parallel solution of sparse linear systems","volume":"64","author":"Kaltofen, Erich","year":"1995","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"6","isbn-type":"print","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/3-540-49264-X_9","article-title":"A block Lanczos algorithm for finding dependencies over \ud835\udc3a\ud835\udc39(2)","author":"Montgomery, Peter L.","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/3540594094"},{"issue":"1","key":"7","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1109\/TIT.1986.1057137","article-title":"Solving sparse linear equations over finite fields","volume":"32","author":"Wiedemann, Douglas H.","year":"1986","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1998-67-224\/S0025-5718-98-00973-9\/S0025-5718-98-00973-9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-224\/S0025-5718-98-00973-9\/S0025-5718-98-00973-9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:51:58Z","timestamp":1776721918000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-224\/S0025-5718-98-00973-9\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"references-count":7,"journal-issue":{"issue":"224","published-print":{"date-parts":[[1998,10]]}},"alternative-id":["S0025-5718-98-00973-9"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-98-00973-9","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[1998]]}}}