Matrix elimination using the 'Method of the Four Russians' (M4RI).The M4RI algorithm was proposed in Gregory Bard; Accelerating Cryptanalysis with the Method of Four Russians; 2006; http://eprint.iacr.org/2006/251
Our implementatation is discussed in in Martin Albrecht and Clément Pernet; Efficient Decomposition of Dense Matrices over GF(2); http://arxiv.org/abs/1006.1744
#include <m4ri/config.h>
#include <stdlib.h>
#include "testing.h"
int ret = 0;
printf("elim: m: %4d, n: %4d ", nr, nc);
printf("A != B ");
ret -= 1;
}
printf("B != C ");
ret -= 1;
}
printf("C != D ");
ret -= 1;
}
printf("D != E ");
ret -= 1;
}
printf("E != F ");
ret -= 1;
}
printf("F != G ");
ret -= 1;
}
printf("G != A ");
ret -= 1;
}
if(ret == 0) {
printf(" ... passed\n");
} else {
printf(" ... FAILED\n");
}
return ret;
}
int main() {
int status = 0;
srandom(17);
status += elim_test_equality(4, 67);
status += elim_test_equality(17, 121);
status += elim_test_equality(65, 17);
status += elim_test_equality(128, 128);
status += elim_test_equality(1024, 1024);
status += elim_test_equality(2047, 2047);
status += elim_test_equality(65, 65);
status += elim_test_equality(100, 100);
status += elim_test_equality(21, 171);
status += elim_test_equality(31, 121);
status += elim_test_equality(193, 65);
status += elim_test_equality(1025, 1025);
status += elim_test_equality(2048, 2048);
status += elim_test_equality(64, 64);
status += elim_test_equality(128, 128);
status += elim_test_equality(4096, 3528);
status += elim_test_equality(1024, 1025);
status += elim_test_equality(1000, 1000);
status += elim_test_equality(1000, 10);
status += elim_test_equality(1710, 1290);
status += elim_test_equality(1290, 1710);
status += elim_test_equality(1290, 1710);
status += elim_test_equality(1290, 1290);
status += elim_test_equality(1000, 210);
if (status == 0) {
printf("All tests passed.\n");
return 0;
} else {
return -1;
}
}
void mzd_top_echelonize_m4ri(mzd_t *M, int k)
Given a matrix in upper triangular form compute the reduced row echelon form of that matrix.
Definition: brilliantrussian.c:965
Main include file for the M4RI library.
int rci_t
Type of row and column indexes.
Definition: misc.h:72
#define TRUE
Pretty for 1.
Definition: misc.h:182
rci_t mzd_echelonize_naive(mzd_t *M, int const full)
Gaussian elimination.
Definition: mzd.c:335
void mzd_randomize(mzd_t *M)
Fill matrix M with uniformly distributed bits.
Definition: mzd.c:1558
void mzd_free(mzd_t *A)
Free a matrix created with mzd_init.
Definition: mzd.c:271
mzd_t * mzd_copy(mzd_t *DST, mzd_t const *A)
Copy matrix A to DST.
Definition: mzd.c:1655
int mzd_equal(mzd_t const *A, mzd_t const *B)
Return TRUE if A == B.
Definition: mzd.c:1605
mzd_t * mzd_init(rci_t const r, rci_t const c)
Create a new matrix of dimension r x c.
Definition: mzd.c:149
Dense matrices over GF(2).
Definition: mzd.h:86