Early termination over small fields

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 behaviour 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.

REFERENCES

• 1: E. R. Berlekamp. Algebraic Coding Theory. McGraw-Hill, 1968.
• 2: J. P. Buhler, H. W. Lenstra, Jr., and C. Pomerance. Factoring integers with the number field sieve. In The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics, pages 50--94. Springer-Verlag, 1993.
• 3: L. Chen, W. Eberly, E. Kaltofen, B. D. Saunders, W. J. Turner, and G. Villard. Efficient matrix preconditioners for black box linear algebra. Linear Algebra and its Applications, 343--344:119--146, 2002.
• 4: D. Coppersmith. Solving linear equations over GF(2); block Lanczos algorithm. Linear Algebra and its Applications, 192:33--60, 1993.
• 5: Jean Louis Dornstetter, On the equivalence between Berlekamp's and Euclid's algorithms, IEEE Transactions on Information Theory, v.33 n.3, p.428-431, May 1, 1987 [doi>10.1109/TIT.1987.1057299]
• 6: W. Eberly. Early termination over small fields. Technical Report 2003-723-26, Department of Computer Science, University of Calgary, May 2003.
• 7: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 8: Erich Kaltofen , Wen-shin Lee , Austin A. Lobo, Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.192-201, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345629]
• 9: Erich Kaltofen , Victor Pan, Processor efficient parallel solution of linear systems over an abstract field, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.180-191, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113396]
• 10: Robert John Lambert , Ian F. Blake, Computational aspects of discrete logarithms, 1996
• 11: C. Lanczos. Solution of systems of linear equations by minimized iterations. J. Res. Nat. Bur. Standards, 49:33--53, 1952.
• 12: Austin Anthony Lobo, Matrix-free linear system solving and applications to symbolic computation, Rensselaer Polytechnic Institute, Troy, NY, 1996
• 13: J. von zur Gathen , Keju Ma, Analysis of Euclidean algorithms for polynomials over finite fields, Journal of Symbolic Computation, v.9 n.4, p.429-455, April 1990 [doi>10.1016/S0747-7171(08)80021-1]
• 14: J. L. Massey. Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory, IT-15:122--127, 1969.
• 15: P. Montgomery. A block Lanczos algorithm for finding dependencies over GF(2). In Advances in Cryptology --- EUROCRYPT '95, volume 921 of Lecture Notes in Computer Science, pages 106--120. Springer, 1995.
• 16: P. Montgomery. Distributed linear algebra. In Proceedings, 4th Workshop on Elliptic Curve Cryptography, 2000.
• 17: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• 18: G. Villard. Further analysis of Coppersmith's block Wiedemann algorithm using matrix polynomials. Rapport de Recherche 975 IM, Institut d'Informatique et de Mathematiques Applicees de Grenoble, 1997.
• 19: D H Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, v.32 n.1, p.54-62, Jan. 1986 [doi>10.1109/TIT.1986.1057137]
• 20: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields; Computations on matrices

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Performance, Reliability, Theory

Keywords:
Berlekamp-Massey algorithm, Lanczos algorithm, black box matrix, early termination, finite field, linear system solution, randomized algorithm