Finite field linear algebra subroutines

ABSTRACT

In this paper we study different implementations of finite field arithmetic, essential foundation of computer algebra. We focus on Galois fields of word size cardinality at most, with any characteristic. Classical representations as machine integers, floating point numbers, polynomials and Zech logarithms are compared. Furthermore, very efficient implementations of finite field dot products, matrix-vector products and matrix-matrix products (namely the symbolic equivalent of level 1, 2 and 3 BLAS) are presented. Our implementations have many symbolic linear algebra applications: symbolic triangularization, system solving, exact determinant computation, matrix normal form are such examples.

REFERENCES

• 1: D. V. Bailey and C. Paar. Efficient arithmetic in finite field extensions with application in elliptic curve cryptography. Journal of Cryptology, 14(3):153-176, 2001.
• 2: Wieb Bosma , John Cannon , Allan Steel, Lattices of compatibly embedded finite fields, Journal of Symbolic Computation, v.24 n.3-4, p.351-369, Sept./Oct. 1997 [doi>10.1006/jsco.1997.0138]
• 3: J. D. Dixon. Exact solution of linear equations using p-adic expansions. Numerische Mathematik, 40:137-141, 1982.
• 4: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 5: J.-G. Dumas. Algorithmes parallèles efficaces pour le calcul formel : algèbre linéaire creuse et extensions algébriques. PhD thesis, Institut National Polytechnique de Grenoble, France, Dec. 2000. ftp://ftp.imag.fr/pub/Mediatheque.IMAG/theses/2000/Dumas.Jean-Guillaume.
• 6: Jean-Guillaume Dumas , Jean-Louis Roch, A parallel block algorithm for exact triangularization of rectangular matrices, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.324-325, July 2001, Crete Island, Greece [doi>10.1145/378580.378743]
• 7: Jean-Guillaume Dumas , B. David Saunders , Gilles Villard, On efficient sparse integer matrix Smith normal form computations, Journal of Symbolic Computation, v.32 n.1, p.71-99, July 2001 [doi>10.1006/jsco.2001.0451]
• 8: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 9: G. H. Golub and C. F. Van Loan. Matrix computations. Johns Hopkins Studies in the Mathematical Sciences. The Johns Hopkins University Press, Baltimore, MD, USA, third edition, 1996.
• 10: J. Grabmeier and A. Scheerhorn. Finite fields in AXIOM. Technical Report TR7/92 (ATR/5) (NP2522), The Numerical Algorithm Group, Downer's Grove, IL, USA and Oxford, UK, 1992.
• 11: Fred G. Gustavson , André Henriksson , Isak Jonsson , Bo Kågström , Per Ling, Recursive Blocked Data Formats and BLAS's for Dense Linear Algebra Algorithms, Proceedings of the 4th International Workshop on Applied Parallel Computing, Large Scale Scientific and Industrial Problems, p.195-206, June 14-17, 1998
• 12: T. Hansen and G. L. Mullen. Primitive polynomials over finite fields. Mathematics of Computation, 59(200):639-643, S47-S50, Oct. 1992.
• 13: K. Huber. Some comments on Zech's logarithm. IEEE Transactions on Information Theory, IT-36:946-950, July 1990.
• 14: Steven Huss-Lederman , Elaine M. Jacobson , Anna Tsao , Thomas Turnbull , Jeremy R. Johnson, Implementation of Strassen's algorithm for matrix multiplication, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.32-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369096]
• 15: O. H. Ibarra, S. Moran, and R. Hui. A generalization of the fast LUP matrix decomposition algorithm and applications. Journal of Algorithms, 3(1):45-56, Mar. 1982.
• 16: E. Kaltofen and G. Villard. On the complexity of computing determinants. In Proceedings of the Fifth Asian Symposium on Computer Mathematics ASCM 2001, volume 9 of Lecture Notes Series on Computing, pages 13-27, Singapore, Sept. 2001.
• 17: Rudolf Lidl , Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, New York, NY, 1986
• 18: P. L. Montgomery. A block Lanczos algorithm for finding dependencies over GF(2). In L. C. Guillou and J.-J. Quisquater, editors, Proceedings of the 1995 International Conference on the Theory and Application of Cryptographic Techniques, Saint-Malo, France, volume 921 of Lecture Notes in Computer Science, pages 106-120, May 1995.
• 19: B. Mourrain and H. Prieto. The ALP reference manual: A framework for symbolic and numeric computations, 2000. www-sop.inria.fr/saga/logiciels/ALP.
• 20: Andrew Odlyzko, Discrete Logarithms: The Past and the Future, Designs, Codes and Cryptography, v.19 n.2-3, p.129-145, March 2000 [doi>10.1023/A:1008350005447]
• 21: C. Pernet. Implementation of Winograd's matrix multiplication over finite fields using ATLAS level 3 BLAS. Technical report, Laboratoire Informatique et Distribution, July 2001. www-id.imag.fr/Apache/RR/RR011122FFLAS.ps.gz.
• 22: B. D. Saunders. Personal communication, 2001.
• 23: V. Shoup. NTL 5.2: A library for doing number theory, 2002. www.shoup.net/ntl.
• 24: R. C. Whaley, A. Petitet, and J. J. Dongarra. Automated empirical optimizations of software and the ATLAS project. Parallel Computing, 27(1-2):3-35, Jan. 2001. www.elsevier.nl/gej-ng/10/35/21/47/25/23/article.pdf.
• 25: H. Zassenhaus. A remark on the Hensel factorization method. Mathematics of Computation, 32(141):287-292, Jan. 1978.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.4 Applications

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Matrix inversion
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

General Terms:
Documentation, Standardization

Keywords:
BLAS level 1-2-3, Galois finite fields, Winograd's symbolic matrix multiplication