M4RI  1.0.1
Defines | Functions
brilliantrussian.h File Reference

M4RI and M4RM. More...

#include <math.h>
#include <string.h>
#include <stdlib.h>
#include "packedmatrix.h"
#include "permutation.h"

Go to the source code of this file.

Defines

#define __M4RI_M4RM_GRAY8
 If defined 8 Gray code tables are used in parallel.

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.
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.
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.
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.
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.
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.
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.
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.
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).
mzd_tmzd_invert_m4ri (mzd_t const *M, mzd_t const *I, int k)
 Invert the matrix M using Konrod's method.
mzd_tmzd_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.
mzd_tmzd_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.
void _mzd_trsm_upper_left_even_m4r (mzd_t const *U, mzd_t *B, int k)

Detailed Description

M4RI and M4RM.

Author:
Gregory Bard <bard@fordham.edu>
Martin Albrecht <martinralbrecht@googlemail.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:
CPreallocated product matrix.
AInput matrix A
BInput matrix B
kM4RI parameter, may be 0 for auto-choose.
clearclear the matrix C first
Author:
Martin Albrecht -- initial implementation
William Hart -- block matrix implementation, use of several Gray code tables, general speed-ups
Ignores offset atrtribute of packedmatrix.
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:
AMatrix to be reduced.
kM4RI parameter, may be 0 for auto-choose.
rRow index.
cColumn index.
max_rOnly clear top max_r rows.
Ignores offset atrtribute of packedmatrix.
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:
CPreallocated product matrix, may be NULL for zero matrix.
AInput matrix A
BInput matrix B
kM4RI parameter, may be 0 for auto-choose.
Ignores offset atrtribute of packedmatrix.
Returns:
Pointer to C.
Examples:
testsuite/test_multiplication.c.
mzd_t* mzd_invert_m4ri ( mzd_t const *  M,
mzd_t const *  I,
int  k 
)

Invert the matrix M using Konrod's method.

To avoid recomputing the identity matrix over and over again, I may be passed in as identity parameter.

Parameters:
MMatrix to be reduced.
IIdentity matrix.
kM4RI parameter, may be 0 for auto-choose.
Ignores offset atrtribute of packedmatrix.
Returns:
Inverse of M
Note:
This function allocates a new matrix for the inverse which must be free'd using mzd_free() once it is not needed anymore.
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:
Mmatrix to generate the tables from
rthe starting row
cthe starting column (only exact up to block)
k
Tprealloced matrix of dimension $2^k$ x m->ncols
Lprealloced table of length $2^k$
Ignores offset atrtribute of packedmatrix.
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:
CPreallocated product matrix, may be NULL for automatic creation.
AInput matrix A
BInput matrix B
kM4RI parameter, may be 0 for auto-choose.
Ignores offset atrtribute of packedmatrix.
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:
MMatrix to operate on
startrowtop row which is operated on
endrowbottom row which is operated on
startcolStarting column for addition
kM4RI parameter
Tcontains the correct row to be added
LContains row number to be added
Ignores offset atrtribute of packedmatrix.
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:
MMatrix to operate on
startrowtop row which is operated on
endrowbottom row which is operated on
startcolStarting column for addition
kM4RI parameter
T0contains the correct row to be added
L0Contains row number to be added
T1contains the correct row to be added
L1Contains row number to be added
Ignores offset atrtribute of packedmatrix.
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:
MMatrix to operate on
startrowtop row which is operated on
endrowbottom row which is operated on
startcolStarting column for addition
kM4RI parameter
T0contains the correct row to be added
L0Contains row number to be added
T1contains the correct row to be added
L1Contains row number to be added
T2contains the correct row to be added
L2Contains row number to be added
Ignores offset atrtribute of packedmatrix.
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:
MMatrix to operate on
startrowtop row which is operated on
endrowbottom row which is operated on
startcolStarting column for addition
kM4RI parameter
T0contains the correct row to be added
L0Contains row number to be added
T1contains the correct row to be added
L1Contains row number to be added
T2contains the correct row to be added
L2Contains row number to be added
T3contains the correct row to be added
L3Contains row number to be added
Ignores offset atrtribute of packedmatrix.
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:
MMatrix to operate on
startrowtop row which is operated on
endrowbottom row which is operated on
startcolStarting column for addition
kM4RI parameter
T0contains the correct row to be added
L0Contains row number to be added
T1contains the correct row to be added
L1Contains row number to be added
T2contains the correct row to be added
L2Contains row number to be added
T3contains the correct row to be added
L3Contains row number to be added
T4contains the correct row to be added
L4Contains row number to be added
Ignores offset atrtribute of packedmatrix.
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:
MMatrix to operate on
startrowtop row which is operated on
endrowbottom row which is operated on
startcolStarting column for addition
kM4RI parameter
T0contains the correct row to be added
L0Contains row number to be added
T1contains the correct row to be added
L1Contains row number to be added
T2contains the correct row to be added
L2Contains row number to be added
T3contains the correct row to be added
L3Contains row number to be added
T4contains the correct row to be added
L4Contains row number to be added
T5contains the correct row to be added
L5Contains row number to be added
Ignores offset atrtribute of packedmatrix.
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:
MMatrix to be reduced.
kM4RI parameter, may be 0 for auto-choose.
Ignores offset atrtribute of packedmatrix.
Examples:
testsuite/test_elimination.c.