Now, that we have a decent PNG reader/writer in M4RI, it’s much easier to get some challenge matrices out of the library. Below, I list and link a few such matrices as they appear during Gröbner basis computations.
|HFE 25 matrix 5 (5.1M)||12307 x 13508||0.07600||1.03||0.59||0.81|
|HFE 30 matrix 5 (16M)||19907 x 29323||0.06731||4.79||2.70||4.76|
|HFE 35 matrix 5 (37M)||29969 x 55800||0.05949||19.33||9.28||19.51|
|Mutant matrix (39M)||26075 x 26407||0.18497||5.71||3.98||2.10|
|random n=24, m=26 matrix 3 (30M)||37587 x 38483||0.03832||20.69||21.08||19.36|
|random n=24_ m=26 matrix 4 (24M)||37576 x 32288||0.04073||18.65||28.44||17.05|
|SR(2,2,2,4) compressed, matrix 2 (328K)||5640 x 14297||0.00333||0.40||0.29||0.18|
|SR(2,2,2,4) compressed, matrix 4 (2.4M)||13665 x 17394||0.01376||2.18||3.04||2.04|
|SR(2,2,2,4) compressed, matrix 5 (2.8M)||11606 x 16282||0.03532||1.94||4.46||1.59|
|SR(2,2,2,4) matrix 6 (1.4M)||13067 x 17511||0.00892||1.90||2.09||1.38|
|SR(2,2,2,4) matrix 7 (1.7M)||12058 x 16662||0.01536||1.53||1.93||1.66|
|SR(2,2,2,4) matrix 9 (36M)||115834 x 118589||0.00376||528.21||578.54||522.98|
The first three rows are from GB computations for the hidden field equations cryptosystem (those matrices were provided by Michael Brickenstein). The “mutant” row is a matrix as it appears during a run of the MXL2 algorithm on a random system (I believe). It was contributed by Wael Said. The rows “random n=25,m=26” are matrices as they appear during a GB computation with PolyBoRi for a random system of equations in 24 variables and 26 equations. The remaining rows are matrices from PolyBoRi computations on small scale AES instances. Those rows which have “compressed” in their description correspond to systems where “linear variables” were eliminate before running the Gröbner basis algorithm.
The last three columns give running times (quite rough ones!) for computing an echelon form (not reduced) using (a) the M4RI algorithm, (b) PLE decomposition and (c) a first implementation of the TRSM for trivial pivots trick. As you can see, currently it’s not straight-forward to pick which strategy to use to eliminate matrices appearing during Gröbner basis computations: the best algorithm to pick varies between different problems and the differences can be dramatic.