1. Martin Albrecht Avatar Martin Albrecht
  2. Untitled project
  3. m4ri

Wiki

Clone wiki

m4ri / Further Reading

View History

Matrix Multiplication

The matrix multiplication machinery in the M4RI library is described in [ABH08].

  • [ABH08] Martin Albrecht, Gregory Bard, William Hart. Algorithm 898: Efficient Multiplication of Dense Matrices over GF(2). ACM Transactions on Mathematical Software (TOMS), 2010. pre-print available at http://arxiv.org/abs/0811.1714

“Method of the Four Russians” Multiplication

This algorithm was created by [ADKF70] for the transitive closure of a graph, then [AHU72] extended it to matrix multiplication over the boolean semiring. A discussion leading to many improvements to the implementation of that algorithm can be followed in [AH08]. A technical report discussing these implementation issues is [ABH08].

  • [ADKF70] V. Arlazarov, E. Dinic, M. Kronrod, and I. Faradzev. On economical construction of the transitive closure of a directed graph. Dokl. Akad. Nauk., 194(11), 1970. (in Russian), English Translation in Soviet Math Dokl.

  • [AHU72] A. Aho, J. Hopcroft, and J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.

  • [AH08] Martin Albrecht, Bill Hart et al. slightly OT: new M4RI library. [sage-devel] mailing list, May 2008. http://groups.google.com/group/sage-devel/...

Strassen Multiplication

The general formula is published in [Str69], the strategy for dealing with extra rows and columns was taken from [BHS08] and the operation schedule from [B08] and [DP08]. An overview of the implementation in the M4RI library is [ABH08].

  • [Str69] Volker Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13:354–356, 1969.

  • [B08] Marco Bodrato. A Strassen-like matrix multiplication suited for squaring and higher power computation. Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, 2010. http://marco.bodrato.it/papers/Bodrato2010-StrassenLikeMatrixMultiplicationForSquares.pdf

  • [BHS08] Robert Bradshaw, David Harvey and William Stein. strassen_window_multiply_c. strassen.pyx, Sage 3.0, 2008. http://www.sagemath.org

  • [DP08] Jean-Guillaume Dumas and Clèment Pernet. Memory efficient scheduling of Strassen-Winograd's matrix multiplication algorithm. arXiv:0707.2347, 2008.

Echelon Forms

M4RI provides two algorithms for computing echelon forms: M4RI and PLE decomposition.

PLE Decomposition

The PLE decomposition and its relationship to other decompositions such as PLUQ is described in [JPS11]. A draft describing our asymptotically fast PLE decomposition implementation and our implementation of block-iterative PLE decomposition is available as [ABP11]. A pre-print of a previous version of this document discussing the Method of Many People Factorisation (MMPF) is available as [AP10].

  • [ABP11] Martin Albrecht, Gregory Bard and Clément Pernet. Efficient Dense Gaussian Elimination over the Finite Field with Two Elements. arXiv:1111.6549v1, 2011.

  • [AP10] Martin Albrecht and Clément Pernet. Efficient Decomposition of Dense Matrices over GF(2). arxiv.org:1006.1744, 2011.

  • [JPS11] Claude-Pierre Jeannerod, Clément Pernet and Arne Storjohann. Rank-profile revealing Gaussian elimination and the CUP matrix decomposition. arxiv.org:1112.571, 2011.

“Method of the Four Russians” Inversion

The algorithm was first published in [Bar06] and is also covered more detailed in [Bar07]. Some implementation details can be found in [AP10].

  • [Bar06] Gregory V. Bard. Accelerating Cryptanalysis with the Method of Four Russians. Cryptology ePrint Archive, Report 2006/251, 2006.

  • [Bar07] Gregory V. Bard. Algorithms for Solving Linear and Polynomial Systems of Equations over Finite Fields with Applications to Cryptanalysis. Phd thesis, University of Maryland, 2007.

Other Publications Referencing M4RI

  • [BR14] Enrico Bertolazzi and Anna Rimoldi. Fast matrix decomposition in F2. Journal of Computational and Applied Mathematics 260 (2014): 519-532.

  • [SLW14] Yao Sun, Dongdai Lin and Dingkang Wang. An improvement over the GVW algorithm for inhomogeneous polynomial systems. arXiv preprint arXiv:1404.1428 (2014).

  • [JPS13] Claude-Pierre Jeannerod, Clément Pernet, and Arne Storjohann. Rank-profile revealing Gaussian elimination and the CUP matrix decomposition. Journal of Symbolic Computation 56 (2013): 46-68.

  • [S13] Willem Sonke. Reconstructing a level-1-network from quartets. Bachelor project at Eindhoven University of Technology, 2013.

  • [HS13] Yann Hamdaoui and Nicolas Sendrier. A Non Asymptotic Analysis of Information Set Decoding. IACR ePrint Report 2013/162, 2013.

  • [TL13] David B. Thomas and Wayne Luk. The LUT-SR family of uniform random number generators for FPGA architectures. Very Large Scale Integration (VLSI) Systems, IEEE Transactions on 21.4 (2013): 761-770.

  • [FT13] Shane T. Fleming and David B. Thomas. Hardware acceleration of matrix multiplication over small prime finite fields. Reconfigurable Computing: Architectures, Tools and Applications. Springer Berlin Heidelberg, 2013. 103-114.

  • [BDEZ12] Razvan Barbulescu, Jeremie Detrey, Nicolas Estibals and Paul Zimmermann. Finding Optimal Formulae for Bilinear Maps. Proceedings of Arithmetic of Finite Fields. LNCS 7369/2102, pages 168-186, Springer 2012.

  • [DP12] Jean-Guillaume Dumas and Clément Pernet. Computational linear algebra over finite fields. Technical report, 2012.

  • [SWHL14] Yao Sun, Dingkang Wang, Z Huang and Dongdai Lin. A Monomial-Oriented GVW for Computing Gr\" obner Bases. arXiv preprint arXiv:1410.0105 (2014).

  • [Ull12] Ehsan Ullah. New Techniques for Polynomial System Solving. Phd thesis at Universität Passau, Germany, 2102.

  • [PTBW11] Albrecht Petzoldt, Enrico Thomae, Stanislav Bulygin and Christopher Wolf. Small Public Keys and Fast Verification for Multivariate Quadratic Public Key Systems. Proceedings of CHES 2011. LNCS Volume 6917/2011, pages 475-490, Springer 2011.

  • [Moh11a] Mohamed Saied Emam Mohamed. Improved Strategies for Solving Multivariate Polynomial Equation Systems over Finite Fields. PhD thesis at TU Darmstadt, 2011.

  • [Moh11b] Wael Said Abdelmageed Mohamed. Improvements for the XL Algorithm with Applications to Algebraic Cryptanalysis. PhD thesis at TU Darmstadt. 2011.

  • [PFJWA11] Agoston Petz, Chien-Liang Fok, Christine Julien, Brenton Walker and Calvin Ardi. Network Coded Routing in Delay Tolerant Networks: An Experience Report. Proceedings of the 3rd Extreme Conference on Communication (ExtremeCom), 2011.

  • [WAPRJ11] Brenton Walker, Calvin Ardi, Agoston Petz, Jung Ryu and Christine Julien. Experiments on the spatial distribution of network code diversity in segmented DTNs. CHANTS '11 Proceedings of the 6th ACM workshop on Challenged networks, 2011.

  • [Alb10] Martin Albrecht. Algorithmic Algebraic Techniques and their Application to Block Cipher Cryptanalysis. Phd thesis at University of London, 2010

  • [Bri10] Michael Brickenstein. Boolean Gröbner bases - Theory, Algorithms and Applications. Phd thesis at TU Kaiserslautern, Germany, 2010

  • [BBDMW10] Johannes Buchmann, Stanislav Bulygin, Jintai Ding, Wael Said Abd Elmageed Mohamed and Fabian Werner. Practical Algebraic Cryptanalysis for Dragon-Based Cryptosystems. Proceedings of 9th International Conference, CANS 2010. 2010.

  • [BCDM10] Johannes Buchmann, Daniel Cabarcas, Jintai Ding and Mohamed Saied Emam Mohamed. Flexible Partial Enlargement to Accelerate Gröbner Basis Computation over F2. Progress in Cryptology – AFRICACRYPT 2010, 2010. http://www.springerlink.com/content/7736225qv8741j3v/

  • [Dem10] Denise Demirel. Effizientes Lösen linearer Gleichungssysteme über GF(2) mit GPUs. Diplomarbeit at TU Darmstadt, 2010.

  • [FL10] Jean-Charles Faugère and Sylvain Lachartre. Parallel Gaussian elimination for Gröbner bases computations in finite fields. Proceedings of the 4th International Workshop on Parallel and Symbolic Computation, 2010. http://portal.acm.org/citation.cfm?id=1837210.1837225

  • [ACPS09] Benny Applebaum, David Cash, Chris Peikert and Amit Sahai. Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems. Advances in Cryptology - CRYPTO 2009, 2009. http://www.springerlink.com/content/mg304504208wq584/

  • [Bar09] Gregory V. Bard. Algebraic Cryptanalysis. Springer Verlag, 2009.

  • [BW09] Nikhil Bansal and Ryan Williams. Regularity Lemmas and Combinatorial Algorithms. 50th Annual IEEE Symposium on Foundations of Computer Science, 2009. http://www.computer.org/portal/web/csdl/doi/10.1109/FOCS.2009.76

  • [MCDBB09] Mohamed Saied Emam Mohamed, Daniel Cabarcas, Jintai Ding, Johannes Buchmann and Stanislav Bulygin. MXL3: An Efficient Algorithm for Computing Gröbner Bases of Zero-Dimensional Ideals. Information, Security and Cryptology – ICISC 2009, 2009. http://www.springerlink.com/content/v0p5729851q404j7/

  • [BB08] Stanislav Bulygin and Michael Brickenstein. Obtaining and Solving Systems of Equations in Key Variables only for the Small Variants of AES. Cryptology ePrint Archive, Report 2008/435, 2008. http://eprint.iacr.org/2008/435

  • [MDB08] Mohamed Saied Emam Mohamed, Jintai Ding and Johannes Buchmann. Algebraic Cryptanalysis of MQQ Public Key Cryptosystem by MutantXL. Cryptology ePrint Archive, Report 2008/451, 2008. http://eprint.iacr.org/2008/451

  • [MMDB08] Mohamed Saied Emam Mohamed, Wael Said Abd Elmageed Mohamed, Jintai Ding and Johannes Buchmann. MXL2: Solving Polynomial Equations over GF(2) Using an Improved Mutant Strategy. Proceedings of Post-Quantum Cryptography 2008, 2008 http://www.cdc.informatik.tu-darmstadt.de/reports/reports/MXL2.pdf

  • [TL09] Jérémie Tharaud and Raphaël Laurent. Linear algebra over the field with two elements using GPUs. Technical report, 2009.

Google Scholar search for references to the M4RI librariy.

How To Cite Us

If you use our libraries in a non-trivial part of your research please consider citing them as follows:

@manual{M4RI,
    key          = "M4RI",
    author       = "Martin Albrecht and Gregory Bard",
    organization = "The M4RI~Team",
    title        = "{The M4RI Library -- Version 20121224}",
    year         = 2012,
    url          = "\url{http://m4ri.sagemath.org}",
}

and cite the appropriate publications mentioned above.

Updated