Early Terminiation over Small Fields
Date
2003-06-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Krylov-based algorithms have recently been used (alone, or in
combination with other methods) in order to solve systems of linear equations
that arise during integer factorization and discrete logarithm computations.
Since these include systems over small finite fields, the behavior of these
algorithms in this setting is of interest. Unfortunately, the application of
these methods is complicated by the possibility of several kinds of breakdown.
Orthogonal vectors can arise when a variant of the Lanczos algorithm is used
to generate a basis, and zero-discrepancies can arise during the computation
of minimal polynomials of linearly recurrent sequences when Wiedemann's
algorithm is applied. Several years ago, Austin Lobo reported experimental
evidence that zero-discrepancies are extremely unlikely when a randomized
version of Wiedemann's algorithm is applied to solve systems over large
fields. With high probability, results are correct if a computation is
terminated as soon as such a sequence is detected. "Early termination" has
consequently been included in recent implementations. In this paper, we
analyze the probability of long sequences of zero-discrepancies during
computations of minimal polynomials of the linearly recurrent sequences that
arise when simple Krylov-based algorithms are used to solve systems over very
small finite fields. Variations of these algorithms that incorporate early
termination are briefly presented and analyzed in the small field case.
Description
Keywords
Computer Science