File: brilliantrussian.h

package info (click to toggle)
libm4ri 20200125-1
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, sid
  • size: 2,560 kB
  • sloc: ansic: 12,633; sh: 4,304; makefile: 137
file content (319 lines) | stat: -rw-r--r-- 10,805 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
/**
 * \file brilliantrussian.h
 * \brief M4RI and M4RM.
 *
 * \author Gregory Bard <bard@fordham.edu>
 * \author 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
 */

#ifndef M4RI_BRILLIANTRUSSIAN_H
#define M4RI_BRILLIANTRUSSIAN_H

 /*******************************************************************
 *
 *                 M4RI:  Linear Algebra over GF(2)
 *
 *    Copyright (C) 2007, 2008 Gregory Bard <bard@fordham.edu>
 *    Copyright (C) 2008-2010 Martin Albrecht <martinralbrecht@googlemail.com>
 *
 *  Distributed under the terms of the GNU General Public License (GPL)
 *  version 2 or higher.
 *
 *    This code is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *    General Public License for more details.
 *
 *  The full text of the GPL is available at:
 *
 *                  http://www.gnu.org/licenses/
 *
 ********************************************************************/

#include <math.h>
#include <string.h>
#include <stdlib.h>

#include <m4ri/mzd.h>
#include <m4ri/mzp.h>

/**
 * \brief Constructs all possible \f$2^k\f$ row combinations using the gray
 * code table.
 * 
 * \param M matrix to generate the tables from
 * \param r the starting row
 * \param c the starting column (only exact up to block)
 * \param k
 * \param T prealloced matrix of dimension \f$2^k\f$ x m->ncols
 * \param L prealloced table of length \f$2^k\f$
 */

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

/**
 * \brief 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).
 *
 * \param M Matrix to operate on
 * \param startrow top row which is operated on
 * \param endrow bottom row which is operated on
 * \param startcol Starting column for addition
 * \param k M4RI parameter
 * \param T contains the correct row to be added
 * \param L Contains row number to be added
 */

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);

/**
 * \brief Same as mzd_process_rows but works with two Gray code tables
 * in parallel.
 *
 * \param M Matrix to operate on
 * \param startrow top row which is operated on
 * \param endrow bottom row which is operated on
 * \param startcol Starting column for addition
 * \param k M4RI parameter
 * \param T0 contains the correct row to be added
 * \param L0 Contains row number to be added
 * \param T1 contains the correct row to be added
 * \param L1 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);

/**
 * \brief Same as mzd_process_rows but works with three Gray code tables
 * in parallel.
 *
 * \param M Matrix to operate on
 * \param startrow top row which is operated on
 * \param endrow bottom row which is operated on
 * \param startcol Starting column for addition
 * \param k M4RI parameter
 * \param T0 contains the correct row to be added
 * \param L0 Contains row number to be added
 * \param T1 contains the correct row to be added
 * \param L1 Contains row number to be added
 * \param T2 contains the correct row to be added
 * \param L2 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);

/**
 * \brief Same as mzd_process_rows but works with four Gray code tables
 * in parallel.
 *
 * \param M Matrix to operate on
 * \param startrow top row which is operated on
 * \param endrow bottom row which is operated on
 * \param startcol Starting column for addition
 * \param k M4RI parameter
 * \param T0 contains the correct row to be added
 * \param L0 Contains row number to be added
 * \param T1 contains the correct row to be added
 * \param L1 Contains row number to be added
 * \param T2 contains the correct row to be added
 * \param L2 Contains row number to be added
 * \param T3 contains the correct row to be added
 * \param L3 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);

/**
 * \brief Same as mzd_process_rows but works with five Gray code tables
 * in parallel.
 *
 * \param M Matrix to operate on
 * \param startrow top row which is operated on
 * \param endrow bottom row which is operated on
 * \param startcol Starting column for addition
 * \param k M4RI parameter
 * \param T0 contains the correct row to be added
 * \param L0 Contains row number to be added
 * \param T1 contains the correct row to be added
 * \param L1 Contains row number to be added
 * \param T2 contains the correct row to be added
 * \param L2 Contains row number to be added
 * \param T3 contains the correct row to be added
 * \param L3 Contains row number to be added
 * \param T4 contains the correct row to be added
 * \param L4 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);

/**
 * \brief Same as mzd_process_rows but works with six Gray code tables
 * in parallel.
 *
 * \param M Matrix to operate on
 * \param startrow top row which is operated on
 * \param endrow bottom row which is operated on
 * \param startcol Starting column for addition
 * \param k M4RI parameter
 * \param T0 contains the correct row to be added
 * \param L0 Contains row number to be added
 * \param T1 contains the correct row to be added
 * \param L1 Contains row number to be added
 * \param T2 contains the correct row to be added
 * \param L2 Contains row number to be added
 * \param T3 contains the correct row to be added
 * \param L3 Contains row number to be added
 * \param T4 contains the correct row to be added
 * \param L4 Contains row number to be added
 * \param T5 contains the correct row to be added
 * \param L5 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);

/**
 * \brief 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
 * 
 * \param M Matrix to be reduced.
 * \param full Return the reduced row echelon form, not only upper triangular form.
 * \param k M4RI parameter, may be 0 for auto-choose.
 *
 * \example tests/test_elimination.c
 * \example tests/bench_elimination.c
 * 
 * \return Rank of A.
 */

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

/**
 * \brief Given a matrix in upper triangular form compute the reduced row
 * echelon form of that matrix.
 * 
 * \param M Matrix to be reduced.
 * \param k M4RI parameter, may be 0 for auto-choose.
 *
 *
 */

void mzd_top_echelonize_m4ri(mzd_t *M, int k);

/**
 * \brief 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).
 * 
 * \param A Matrix to be reduced.
 * \param k M4RI parameter, may be 0 for auto-choose.
 * \param r Row index.
 * \param c Column index.
 * \param max_r Only clear top max_r rows.
 *
 *
 */

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

/**
 * \brief Invert the matrix src using Konrod's method.
 *
 * \param dst Matrix to hold the inverse (may be NULL)
 * \param src Matrix to be inverted.
 * \param k Table size parameter, may be 0 for automatic choice.
 *
 *
 * \return Inverse of src if src has full rank
 */

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

/**
 * \brief 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.
 *
 * \param C Preallocated product matrix, may be NULL for automatic creation.
 * \param A Input matrix A
 * \param B Input matrix B
 * \param k M4RI parameter, may be 0 for auto-choose.
 *
 *
 * \return Pointer to C.
 */

mzd_t *mzd_mul_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.
 *
 * \param C Preallocated product matrix, may be NULL for zero matrix.
 * \param A Input matrix A
 * \param B Input matrix B
 * \param k M4RI parameter, may be 0 for auto-choose.
 *
 *
 * \return Pointer to C.
 */

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

/**
 * \brief 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
 *
 * \param C Preallocated product matrix.
 * \param A Input matrix A
 * \param B Input matrix B
 * \param k M4RI parameter, may be 0 for auto-choose.
 * \param clear clear the matrix C first
 *
 * \author Martin Albrecht -- initial implementation
 * \author William Hart -- block matrix implementation, use of several
 * Gray code tables, general speed-ups
 *
 *
 * \return Pointer to C.
 */

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


#endif // M4RI_BRILLIANTRUSSIAN_H