Further Reading

Matrix Multiplication

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

[ABH08] Martin Albrecht, Gregory Bard, William Hart. Efficient Multiplication of Dense Matrices over GF(2). arXiv:i0811.1714, 2008. 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 highest power computation. Preprint N.622 Centro Interdipartimentale "Vito Volterra" - Università di Roma "Tor Vergata". http://bodrato.it/papers/#CIVV2008

[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

Echelon Forms

So far, only the “Method of the Four Russians” is implemented.

“Method of the Four Russians” Inversion

The algorithm was first published in [Bar06] and is also covered more detailed in [Bar07].

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

Publications Citing/Using/Mentioning M4RI

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

If you use this library in a non-trivial part of your research please consider citing it as follows:

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

and cite the appropriate publications mentioned above.