Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm

ABSTRACT

In this paper we describe how the half-gcd algorithm can be adapted in order to speed up the sequential stage of Coppersmith's block Wiedemann algorithm for solving large sparse linear systems over any finite field. This very stage solves a sub-problem than can be seen as the computation of a linear generator for a matrix sequence. Our primary realm of interest is the field Fq for large prime power q. For the solution of a N × N system, the complexity of this sequential part drops from &Ogr;(N²) to &Ogr;(M(N) log N) where M(d) is the cost for multiplying two polynomials of degree d. We discuss the implications of this improvement for the overall cost of the block Wiedemann algorithm and how its parameters should be chosen for best efficiency.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Bernhard Beckermann , George Labahn, A Uniform Approach for the Fast Computation of Matrix-Type Pade Approximants, SIAM Journal on Matrix Analysis and Applications, v.15 n.3, p.804-823, July 1994 [doi>10.1137/S0895479892230031]
• 3: BITMEAD, R.. R., AND ANDERSON, B. D. O. Asymptotically fast solution of Toeplitz and related systems of linear equations. Linear Algebra Appl. 34 (1980), 103- 116.
• 4: CABAL. 233-digit SNFS factorization, ftp://ftp.cwi. nl/pub/herman/SNFSrecords/SNFS-233, Nov. 2000.
• 5: Stefania Cavallar, Strategies in Filtering in the Number Field Sieve, Proceedings of the 4th International Symposium on Algorithmic Number Theory, p.209-232, July 02-07, 2000
• 6: CAVALLAR, S., ET AL. Factorization of a 512-bit RSA modulus. In Proc. EUROCRYPT 2000 (2000), B. Preneel, Ed., vol. 1807 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 1-18.
• 7: COPPERSMITH, D. Fast evaluation of logarithms in fields of characteristic two. IEEE Trans. Inform. Theory IT-30, 4 (July 1984), 587-594.
• 8: COPPERSMITH, D. Solving linear equations over GF(2): Block Lanczos algorithm. Linear Algebra Appl. 192 (Jan. 1993), 33-60.
• 9: Don Coppersmith, Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm, Mathematics of Computation, v.62 n.205, p.333-350, Jan. 1994 [doi>10.2307/2153413]
• 10: 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]
• 11: GAUDRY, P. An algorithm for solving the discrete log problem on hyperelliptic curves. In Proc. EURO- CRYPT 2000 (2000), B. Preneel, Ed., vol. 1807 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 19-34.
• 12: GAUDRY, P. Algorithmique des courbes hyperelliptiques et applications d la cryptologie. Thse, tcole Polytechnique, Dec. 2000.
• 13: GUSTAVSON, F. G., AND YUN, D. Y. Fast algorithms for rational Hermite approximation and solution of Toeplitz systems. IEEE Transactions on Circuits and Systems CAS-26, 9 (Sept. 1979), 750-755.
• 14: Erich Kaltofen, Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems, Mathematics of Computation, v.64 n.210, p.777-806, April 1995 [doi>10.2307/2153451]
• 15: KALTOFEN, E., AND LOBO, A. Distributed matrix-free solution of large sparse linear systems over finite fields. Algorithmica 24 (1999), 331-348.
• 16: Brian A. LaMacchia , Andrew M. Odlyzko, Solving Large Sparse Linear Systems over Finite Fields, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.109-133, August 11-15, 1990
• 17: MONTGOMERY, P. L. A block Lanczos algorithm for finding dependencies over GF(2). In Proc. EURO- CRYPT '95 (1995), L. C. GuiUou and J.-J. Quisquater, Eds., vol. 921 of Lecture Notes in Comput. Sei., pp. 106-120.
• 18: MORF, M. Doubling algorithms for Toeplitz and related equations. In Proc. IEEE Internat. Conference Acoustics, Speech and Signal Processing (1980), IEEE, pp. 954-959.
• 19: A M Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, Proc. of the EUROCRYPT 84 workshop on Advances in cryptology: theory and application of cryptographic techniques, p.224-314, December 1985, Paris, France
• 20: POMERANCE, C., AND SMITH, J. W. Reduction of huge, sparse matrices over finite fields via created catastrophes. Experiment. Math. 1, 2 (1992), 89-94.
• 21: Jeremy Teitelbaum, Euclid's algorithm and the lanczos method over finite fields, Mathematics of Computation, v.67 n.224, p.1665-1678, Oct. 1998 [doi>10.1090/S0025-5718-98-00973-9]
• 22: VILLARD, G. A study of Coppersmith's block Wiedemann algorithm using matrix polynomials. Research Report 975, LMC-IMAG, Grenoble, France, Apr. 1997.
• 23: G. Villard, Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems (extended abstract), Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.32-39, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258742]
• 24: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 25: Damian Weber , Thomas F. Denny, The Solution of McCurley's Discrete Log Challenge, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.458-471, August 23-27, 1998
• 26: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.0 General

General Terms:
Algorithms, Performance, Verification