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. http://arxiv.org/abs/0707.2347

Travolta Table Multiplication

The idea is to precompute all possible multiples of a row and to store those multiples in a lookup table. No formal presentation of the idea is known to the authors.

Echelon Forms

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

PLS Decomposition

A pre-print describing our asymptotically fast PLS decomposition implementation and the Method of Many People Factorisation (MMPF) is available in [AP10].

[AP10] Martin Albrecht and Clément Pernet. Efficient Decomposition of Dense Matrices over GF(2). pre-print.

“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. http://eprint.iacr.org/2006/251

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

Travolta Table Elimination

The idea is to precompute all possible multiples of a row and to store those multiples in a lookup table. No formal presentation of the idea is known to the authors.

Other Publications Citing/Using/Mentioning M4RI(e)

[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

[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/

[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/

[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/

[BB09] Tomas J. Boothby and Robert W. Bradshaw. Bitslicing and the Method of Four Russians Over Larger Finite Fields. arXiv:0901.1413v1, 2009. http://arxiv.org/abs/0901.1413

[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

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 20100817}",
    year         = 2010,
    url          = "\url{http://m4ri.sagemath.org}",
}
@manual{M4RIE,
    key          = "M4RIE",
    author       = "Martin Albrecht"
    organization = "The M4RI~Team",
    title        = "{The M4RIE Library -- Version 20100817}",
    year         = 2010,
    url          = "\url{http://m4ri.sagemath.org}",
}

and cite the appropriate publications mentioned above.

M4RI(e)- Linear Algebra over $\mathbb{F}_2$ (and $\mathbb{F}_{2^e}$)

Menu

Development

M4RI

M4RIE

Links

Further Reading

Matrix Multiplication

“Method of the Four Russians” Multiplication