M4RI and M4RM. More...

#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <m4ri/mzd.h>
#include <m4ri/mzp.h>

Functions
void	mzd_make_table (mzd_t const M, rci_t r, rci_t c, int k, mzd_t T, rci_t *L)
	Constructs all possible \(2^k\) row combinations using the gray code table. More...

void	mzd_process_rows (mzd_t M, rci_t startrow, rci_t endrow, rci_t startcol, int k, mzd_t const T, rci_t const *L)
	The function looks up k bits from position i,startcol in each row and adds the appropriate row from T to the row i. More...

void	mzd_process_rows2 (mzd_t M, rci_t startrow, rci_t endrow, rci_t startcol, int k, mzd_t const T0, rci_t const L0, mzd_t const T1, rci_t const *L1)
	Same as mzd_process_rows but works with two Gray code tables in parallel. More...

void	mzd_process_rows3 (mzd_t M, rci_t startrow, rci_t endrow, rci_t startcol, int k, mzd_t const T0, rci_t const L0, mzd_t const T1, rci_t const L1, mzd_t const T2, rci_t const *L2)
	Same as mzd_process_rows but works with three Gray code tables in parallel. More...

void	mzd_process_rows4 (mzd_t M, rci_t startrow, rci_t endrow, rci_t startcol, int k, mzd_t const T0, rci_t const L0, mzd_t const T1, rci_t const L1, mzd_t const T2, rci_t const L2, mzd_t const T3, rci_t const *L3)
	Same as mzd_process_rows but works with four Gray code tables in parallel. More...

void	mzd_process_rows5 (mzd_t M, rci_t startrow, rci_t endrow, rci_t startcol, int k, mzd_t const T0, rci_t const L0, mzd_t const T1, rci_t const L1, mzd_t const T2, rci_t const L2, mzd_t const T3, rci_t const L3, mzd_t const T4, rci_t const *L4)
	Same as mzd_process_rows but works with five Gray code tables in parallel. More...

void	mzd_process_rows6 (mzd_t M, rci_t startrow, rci_t endrow, rci_t startcol, int k, mzd_t const T0, rci_t const L0, mzd_t const T1, rci_t const L1, mzd_t const T2, rci_t const L2, mzd_t const T3, rci_t const L3, mzd_t const T4, rci_t const L4, mzd_t const T5, rci_t const *L5)
	Same as mzd_process_rows but works with six Gray code tables in parallel. More...

rci_t	_mzd_echelonize_m4ri (mzd_t *A, const int full, int k, int heuristic, const double threshold)

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

rci_t	_mzd_top_echelonize_m4ri (mzd_t *A, int k, rci_t r, rci_t c, rci_t max_r)
	Given a matrix in upper triangular form compute the reduced row echelon form of that matrix but only start to do anything for the pivot at (r,c). More...

mzd_t *	mzd_inv_m4ri (mzd_t dst, const mzd_t src, int k)
	Invert the matrix src using Konrod's method. More...

mzd_t *	mzd_mul_m4rm (mzd_t C, mzd_t const A, mzd_t const *B, int k)
	Matrix multiplication using Konrod's method, i.e. compute C such that C == AB. More...

mzd_t *	mzd_addmul_m4rm (mzd_t C, mzd_t const A, mzd_t const *B, int k)

mzd_t *	_mzd_mul_m4rm (mzd_t C, mzd_t const A, mzd_t const *B, int k, int clear)
	Matrix multiplication using Konrod's method, i.e. compute C such that C == AB. More...

Detailed Description

M4RI and M4RM.

Author: Gregory Bard bard@.nosp@m.ford.nosp@m.ham.e.nosp@m.du; Martin Albrecht marti.nosp@m.nral.nosp@m.brech.nosp@m.t@go.nosp@m.oglem.nosp@m.ail..nosp@m.com

Note: For reference see Gregory Bard; Accelerating Cryptanalysis with the Method of Four Russians; 2006; http://eprint.iacr.org/2006/251.pdf

Function Documentation

rci_t _mzd_echelonize_m4ri	(	mzd_t *	A,
		const int	full,
		int	k,
		int	heuristic,
		const double	threshold
	)

General algorithm

Step 1.Denote the first column to be processed in a given iteration as \(a_i\). Then, perform Gaussian elimination on the first \(3k\) rows after and including the \(i\)-th row to produce an identity matrix in \(a_{i,i} ... a_{i+k-1,i+k-1},\) and zeroes in \(a_{i+k,i} ... a_{i+3k-1,i+k-1}\).

Step 2. Construct a table consisting of the \(2^k\) binary strings of length k in a Gray code. Thus with only \(2^k\) vector additions, all possible linear combinations of these k rows have been precomputed.

Step 3. One can rapidly process the remaining rows from \(i + 3k\) until row \(m\) (the last row) by using the table. For example, suppose the \(j\)-th row has entries \(a_{j,i} ... a_{j,i+k-1}\) in the columns being processed. Selecting the row of the table associated with this k-bit string, and adding it to row j will force the k columns to zero, and adjust the remaining columns from \( i + k\) to n in the appropriate way, as if Gaussian elimination had been performed.

Step 4. While the above form of the algorithm will reduce a system of boolean linear equations to unit upper triangular form, and thus permit a system to be solved with back substitution, the M4RI algorithm can also be used to invert a matrix, or put the system into reduced row echelon form (RREF). Simply run Step 3 on rows \(0 ... i-1\) as well as on rows \(i + 3k ... m\). This only affects the complexity slightly, changing the 2.5 coeffcient to 3.

Attention: This function implements a variant of the algorithm described above. If heuristic is true, then this algorithm, will switch to PLUQ based echelon form computation once the density reaches the threshold.

mzd_t* _mzd_mul_m4rm	(	mzd_t *	C,
		mzd_t const *	A,
		mzd_t const *	B,
		int	k,
		int	clear
	)

Matrix multiplication using Konrod's method, i.e. compute C such that C == AB.

This is the actual implementation.

This function is described in Martin Albrecht, Gregory Bard and William Hart; Efficient Multiplication of Dense Matrices over GF(2); pre-print available at http://arxiv.org/abs/0811.1714

Parameters

C	Preallocated product matrix.
A	Input matrix A
B	Input matrix B
k	M4RI parameter, may be 0 for auto-choose.
clear	clear the matrix C first

Author: Martin Albrecht – initial implementation; William Hart – block matrix implementation, use of several Gray code tables, general speed-ups

Returns: Pointer to C.

The algorithm proceeds as follows:

Step 1. Make a Gray code table of all the \(2^k\) linear combinations of the \(k\) rows of \(B_i\). Call the \(x\)-th row \(T_x\).

Step 2. Read the entries \(a_{j,(i-1)k+1}, a_{j,(i-1)k+2} , ... , a_{j,(i-1)k+k}.\)

Let \(x\) be the \(k\) bit binary number formed by the concatenation of \(a_{j,(i-1)k+1}, ... , a_{j,ik}\).

Step 3. for \(h = 1,2, ... , c\) do calculate \(C_{jh} = C_{jh} + T_{xh}\).

rci_t _mzd_top_echelonize_m4ri	(	mzd_t *	A,
		int	k,
		rci_t	r,
		rci_t	c,
		rci_t	max_r
	)

Given a matrix in upper triangular form compute the reduced row echelon form of that matrix but only start to do anything for the pivot at (r,c).

Parameters

A	Matrix to be reduced.
k	M4RI parameter, may be 0 for auto-choose.
r	Row index.
c	Column index.
max_r	Only clear top max_r rows.

mzd_t* mzd_addmul_m4rm	(	mzd_t *	C,
		mzd_t const *	A,
		mzd_t const *	B,
		int	k
	)

Set C to C + AB using Konrod's method.

This is the convenient wrapper function, please see _mzd_mul_m4rm for authors and implementation details.

Parameters

C	Preallocated product matrix, may be NULL for zero matrix.
A	Input matrix A
B	Input matrix B
k	M4RI parameter, may be 0 for auto-choose.

Returns: Pointer to C.

Examples:: testsuite/test_multiplication.c.

mzd_t* mzd_inv_m4ri	(	mzd_t *	dst,
		const mzd_t *	src,
		int	k
	)

Invert the matrix src using Konrod's method.

Parameters

dst	Matrix to hold the inverse (may be NULL)
src	Matrix to be inverted.
k	Table size parameter, may be 0 for automatic choice.

Returns: Inverse of src if src has full rank

void mzd_make_table	(	mzd_t const *	M,
		rci_t	r,
		rci_t	c,
		int	k,
		mzd_t *	T,
		rci_t *	L
	)

Constructs all possible \(2^k\) row combinations using the gray code table.

Parameters

M	matrix to generate the tables from
r	the starting row
c	the starting column (only exact up to block)
k
T	prealloced matrix of dimension \(2^k\) x m->ncols
L	prealloced table of length \(2^k\)

mzd_t* mzd_mul_m4rm	(	mzd_t *	C,
		mzd_t const *	A,
		mzd_t const *	B,
		int	k
	)

Matrix multiplication using Konrod's method, i.e. compute C such that C == AB.

This is the convenient wrapper function, please see _mzd_mul_m4rm for authors and implementation details.

Parameters

C	Preallocated product matrix, may be NULL for automatic creation.
A	Input matrix A
B	Input matrix B
k	M4RI parameter, may be 0 for auto-choose.

Returns: Pointer to C.

Examples:: testsuite/test_multiplication.c.

void mzd_process_rows	(	mzd_t *	M,
		rci_t	startrow,
		rci_t	endrow,
		rci_t	startcol,
		int	k,
		mzd_t const *	T,
		rci_t const *	L
	)

The function looks up k bits from position i,startcol in each row and adds the appropriate row from T to the row i.

This process is iterated for i from startrow to stoprow (exclusive).

Parameters

M	Matrix to operate on
startrow	top row which is operated on
endrow	bottom row which is operated on
startcol	Starting column for addition
k	M4RI parameter
T	contains the correct row to be added
L	Contains row number to be added

void mzd_process_rows2	(	mzd_t *	M,
		rci_t	startrow,
		rci_t	endrow,
		rci_t	startcol,
		int	k,
		mzd_t const *	T0,
		rci_t const *	L0,
		mzd_t const *	T1,
		rci_t const *	L1
	)

Same as mzd_process_rows but works with two Gray code tables in parallel.

Parameters

M	Matrix to operate on
startrow	top row which is operated on
endrow	bottom row which is operated on
startcol	Starting column for addition
k	M4RI parameter
T0	contains the correct row to be added
L0	Contains row number to be added
T1	contains the correct row to be added
L1	Contains row number to be added

void mzd_process_rows3	(	mzd_t *	M,
		rci_t	startrow,
		rci_t	endrow,
		rci_t	startcol,
		int	k,
		mzd_t const *	T0,
		rci_t const *	L0,
		mzd_t const *	T1,
		rci_t const *	L1,
		mzd_t const *	T2,
		rci_t const *	L2
	)

Same as mzd_process_rows but works with three Gray code tables in parallel.

Parameters

M	Matrix to operate on
startrow	top row which is operated on
endrow	bottom row which is operated on
startcol	Starting column for addition
k	M4RI parameter
T0	contains the correct row to be added
L0	Contains row number to be added
T1	contains the correct row to be added
L1	Contains row number to be added
T2	contains the correct row to be added
L2	Contains row number to be added

void mzd_process_rows4	(	mzd_t *	M,
		rci_t	startrow,
		rci_t	endrow,
		rci_t	startcol,
		int	k,
		mzd_t const *	T0,
		rci_t const *	L0,
		mzd_t const *	T1,
		rci_t const *	L1,
		mzd_t const *	T2,
		rci_t const *	L2,
		mzd_t const *	T3,
		rci_t const *	L3
	)

Same as mzd_process_rows but works with four Gray code tables in parallel.

Parameters

M	Matrix to operate on
startrow	top row which is operated on
endrow	bottom row which is operated on
startcol	Starting column for addition
k	M4RI parameter
T0	contains the correct row to be added
L0	Contains row number to be added
T1	contains the correct row to be added
L1	Contains row number to be added
T2	contains the correct row to be added
L2	Contains row number to be added
T3	contains the correct row to be added
L3	Contains row number to be added

void mzd_process_rows5	(	mzd_t *	M,
		rci_t	startrow,
		rci_t	endrow,
		rci_t	startcol,
		int	k,
		mzd_t const *	T0,
		rci_t const *	L0,
		mzd_t const *	T1,
		rci_t const *	L1,
		mzd_t const *	T2,
		rci_t const *	L2,
		mzd_t const *	T3,
		rci_t const *	L3,
		mzd_t const *	T4,
		rci_t const *	L4
	)

Same as mzd_process_rows but works with five Gray code tables in parallel.

Parameters

M	Matrix to operate on
startrow	top row which is operated on
endrow	bottom row which is operated on
startcol	Starting column for addition
k	M4RI parameter
T0	contains the correct row to be added
L0	Contains row number to be added
T1	contains the correct row to be added
L1	Contains row number to be added
T2	contains the correct row to be added
L2	Contains row number to be added
T3	contains the correct row to be added
L3	Contains row number to be added
T4	contains the correct row to be added
L4	Contains row number to be added

void mzd_process_rows6	(	mzd_t *	M,
		rci_t	startrow,
		rci_t	endrow,
		rci_t	startcol,
		int	k,
		mzd_t const *	T0,
		rci_t const *	L0,
		mzd_t const *	T1,
		rci_t const *	L1,
		mzd_t const *	T2,
		rci_t const *	L2,
		mzd_t const *	T3,
		rci_t const *	L3,
		mzd_t const *	T4,
		rci_t const *	L4,
		mzd_t const *	T5,
		rci_t const *	L5
	)

Same as mzd_process_rows but works with six Gray code tables in parallel.

Parameters

M	Matrix to operate on
startrow	top row which is operated on
endrow	bottom row which is operated on
startcol	Starting column for addition
k	M4RI parameter
T0	contains the correct row to be added
L0	Contains row number to be added
T1	contains the correct row to be added
L1	Contains row number to be added
T2	contains the correct row to be added
L2	Contains row number to be added
T3	contains the correct row to be added
L3	Contains row number to be added
T4	contains the correct row to be added
L4	Contains row number to be added
T5	contains the correct row to be added
L5	Contains row number to be added

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.

Parameters

M	Matrix to be reduced.
k	M4RI parameter, may be 0 for auto-choose.

Examples:: testsuite/test_elimination.c.

Functions

Detailed Description

Function Documentation