1 #ifndef M4RIE_MZD_PTR_H
2 #define M4RIE_MZD_PTR_H
3
4 /******************************************************************************
5 *
6 * M4RIE: Linear Algebra over GF(2^e)
7 *
8 * Copyright (C) 2013 Martin Albrecht <martinralbrecht@googlemail.com>
9 *
10 * Distributed under the terms of the GNU General Public License (GEL)
11 * version 2 or higher.
12 *
13 * This code is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * The full text of the GPL is available at:
19 *
20 * http://www.gnu.org/licenses/
21 ******************************************************************************/
22
23 #include <stdarg.h>
24 #include <m4rie/gf2e.h>
25 #include <m4ri/djb.h>
26
27 /**
28 * \brief Add A to coefficient of X^t but perform modular reductions on the fly.
29 *
30 * (A + X^t % minpoly)
31 *
32 * \param ff Finite field (must not be NULL)
33 * \param A Matrix
34 * \param X Matrix list
35 * \param t Integer >= 0 (degree)
36 */
37
_mzd_ptr_add_modred(const gf2e * ff,const mzd_t * A,mzd_t ** X,const int t)38 static inline void _mzd_ptr_add_modred(const gf2e *ff, const mzd_t *A, mzd_t **X, const int t) {
39 if (mzd_is_zero(A))
40 return;
41
42 if ((ff==NULL) || (t < ff->degree)) {
43 mzd_add(X[t], X[t], A);
44 return;
45 }
46
47 word pow_gen = ff->pow_gen[t];
48
49 for(int i=0; i<ff->degree; i++) {
50 if (pow_gen & (1<<i))
51 mzd_add(X[i],X[i],A);
52 }
53 }
54
55 /**
56 * \brief Add A to n coefficients but perform modular reductions on the fly (if ff != NULL).
57 *
58 * \param ff Finite field (may be NULL)
59 * \param A Matrix
60 * \param X Matrix list
61 * \param n Integer > 0
62 */
63
_mzd_ptr_add_to_all(const gf2e * ff,mzd_t * A,mzd_t ** X,const int n,...)64 static inline mzd_t *_mzd_ptr_add_to_all(const gf2e *ff, mzd_t *A, mzd_t **X, const int n, ...) {
65 va_list b_list;
66 va_start( b_list, n );
67
68 if (ff)
69 for( int i = 0 ; i < n; i++ ) {
70 int t = va_arg(b_list, int);
71 _mzd_ptr_add_modred(ff, A, X, t);
72 }
73 else
74 for( int i = 0 ; i < n; i++ ) {
75 int t = va_arg(b_list, int);
76 mzd_add(X[t], X[t], A);
77 }
78
79 va_end( b_list );
80 return A;
81 }
82
_mzd_ptr_add(mzd_t ** c,const mzd_t ** a,const mzd_t ** b,const deg_t length)83 static inline void _mzd_ptr_add(mzd_t **c, const mzd_t **a, const mzd_t **b, const deg_t length) {
84 switch(length) {
85 case 32: mzd_add(c[31], a[31], b[31]);
86 case 31: mzd_add(c[30], a[30], b[30]);
87 case 30: mzd_add(c[29], a[29], b[29]);
88 case 29: mzd_add(c[28], a[28], b[28]);
89 case 28: mzd_add(c[27], a[27], b[27]);
90 case 27: mzd_add(c[26], a[26], b[26]);
91 case 26: mzd_add(c[25], a[25], b[25]);
92 case 25: mzd_add(c[24], a[24], b[24]);
93 case 24: mzd_add(c[23], a[23], b[23]);
94 case 23: mzd_add(c[22], a[22], b[22]);
95 case 22: mzd_add(c[21], a[21], b[21]);
96 case 21: mzd_add(c[20], a[20], b[20]);
97 case 20: mzd_add(c[19], a[19], b[19]);
98 case 19: mzd_add(c[18], a[18], b[18]);
99 case 18: mzd_add(c[17], a[17], b[17]);
100 case 17: mzd_add(c[16], a[16], b[16]);
101 case 16: mzd_add(c[15], a[15], b[15]);
102 case 15: mzd_add(c[14], a[14], b[14]);
103 case 14: mzd_add(c[13], a[13], b[13]);
104 case 13: mzd_add(c[12], a[12], b[12]);
105 case 12: mzd_add(c[11], a[11], b[11]);
106 case 11: mzd_add(c[10], a[10], b[10]);
107 case 10: mzd_add(c[ 9], a[ 9], b[ 9]);
108 case 9: mzd_add(c[ 8], a[ 8], b[ 8]);
109 case 8: mzd_add(c[ 7], a[ 7], b[ 7]);
110 case 7: mzd_add(c[ 6], a[ 6], b[ 6]);
111 case 6: mzd_add(c[ 5], a[ 5], b[ 5]);
112 case 5: mzd_add(c[ 4], a[ 4], b[ 4]);
113 case 4: mzd_add(c[ 3], a[ 3], b[ 3]);
114 case 3: mzd_add(c[ 2], a[ 2], b[ 2]);
115 case 2: mzd_add(c[ 1], a[ 1], b[ 1]);
116 case 1: mzd_add(c[ 0], a[ 0], b[ 0]);
117 case 0:
118 break;
119 default:
120 for(deg_t i=0; i<length; i++)
121 mzd_add(c[ i], a[ i], b[ i]);
122 }
123 }
124
125 /** karatsuba.c **/
126
127 /**
128 * \brief \f$ X += A \cdot B \f$ over \GF4 using 3 multiplications over \GF2 and 2 temporary \GF2 matrices.
129 *
130 * If no finite field is given, polynomial arithmetic with polynomials of degree 1 is performed. In
131 * this case, X is expected to have at least length 3. If a finite field is given, then C is
132 * expected to have at least length 2.
133 *
134 * The formula was taken from Peter L. Montgomery. "Five, Six, and
135 * Seven-Term Karatsuba-Like Formulae" in IEEE TRANSACTIONS ON
136 * COMPUTERS, VOL. 54, NO. 3, MARCH 2005/
137 *
138 * \param ff Finite Field, may be NULL for polynomial arithmetic.
139 * \param X Preallocated return matrix, of length >= 2 (ff != NULL) or >=3 (ff == NULL)
140 * \param A Input matrix A, preallocated of length >= 2.
141 * \param B Input matrix B, preallocated of length >= 2.
142 *
143 * \sa _mzd_ptr_addmul_karatsuba()
144 *
145 * \ingroup Multiplication
146 */
147
148 void _mzd_ptr_addmul_karatsuba2(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B);
149
150 /**
151 * \brief \f$ X += A \cdot B \f$ over \GF8 using 6 multiplications over \GF2 and 3 temporary \GF2 matrices..
152 */
153
154 void _mzd_ptr_addmul_karatsuba3(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B);
155
156 /**
157 * \brief \f$ X += A \cdot B \f$ over \GF16 using 9 multiplications over \GF2 and 3 temporary \GF2 matrices.
158 */
159
160 void _mzd_ptr_addmul_karatsuba4(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B);
161
162 /**
163 * \brief \f$ C += A \cdot B \f$ over \GF32 using 13 multiplications over \GF2 and 3 temporary \GF2 matrices..
164 */
165
166 void _mzd_ptr_addmul_karatsuba5(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B);
167
168 /**
169 * \brief \f$ C += A \cdot B \f$ over \GF64 using 17 multiplications over \GF2 and 3 temporary \GF2 matrices.
170 */
171
172 void _mzd_ptr_addmul_karatsuba6(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B);
173
174 /**
175 * \brief \f$ X += A \cdot B \f$ over \GF128 using 22 multiplications over \GF2 and 3 temporary \GF2 matrices.
176 */
177
178 void _mzd_ptr_addmul_karatsuba7(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B);
179
180 /**
181 * \brief \f$ X += A \cdot B \f$ over \GF256 using 27 multiplications over \GF2 and 3 temporary \GF2 matrices.
182 */
183
184 void _mzd_ptr_addmul_karatsuba8(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B);
185
186 /**
187 * \brief \f$ X += A \cdot B \f$ over \GF512 using 31 multiplications over \GF2 and 3 temporary \GF2 matrices.
188 */
189
190 void _mzd_ptr_addmul_karatsuba9(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B);
191
192 /**
193 * \brief \f$ X += A \cdot B \f$ over \GF1024 using 36 multiplications over \GF2 and 3 temporary \GF2 matrices.
194 */
195
196 void _mzd_ptr_addmul_karatsuba10(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B);
197
198 /**
199 * \brief \f$ X += A \cdot B \f$ over \GF2048 using 40 multiplications over \GF2 and 3 temporary \GF2 matrices.
200 */
201
202 void _mzd_ptr_addmul_karatsuba11(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B);
203
204 /**
205 * \brief \f$ X += A \cdot B \f$ over \GF4096 using 45 multiplications over \GF2 and 3 temporary \GF2 matrices.
206 */
207
208 void _mzd_ptr_addmul_karatsuba12(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B);
209
210 /**
211 * \brief \f$ X += A \cdot B \f$ over \GF8192 using 49 multiplications over \GF2 and 3 temporary \GF2 matrices.
212 */
213
214 void _mzd_ptr_addmul_karatsuba13(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B);
215
216 /**
217 * \brief \f$ X += A \cdot B \f$ over \GF16384 using 55 multiplications over \GF2 and 3 temporary \GF2 matrices.
218 */
219
220 void _mzd_ptr_addmul_karatsuba14(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B);
221
222 /**
223 * \brief \f$ X += A \cdot B \f$ over \GF32768 using 60 multiplications over \GF2 and 3 temporary \GF2 matrices.
224 */
225
226 void _mzd_ptr_addmul_karatsuba15(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B);
227
228 /**
229 * \brief \f$ X += A \cdot B \f$ over \GF65536 using 64 multiplications over \GF2 and 3 temporary \GF2 matrices.
230 */
231
232 void _mzd_ptr_addmul_karatsuba16(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B);
233
234
235 /**
236 * W = m*V
237 *
238 * Apply the linear map m to V (considered as a vector) and write the result to W.
239 *
240 * \param m Linear map
241 * \param W Output vector of matrices mod 2.
242 * \oaram V Input vector of matrices mod 2.
243 */
244
245 void djb_apply_mzd_ptr(djb_t *m, mzd_t **W, const mzd_t **V);
246
247 #endif //M4RIE_MZD_PTR_H
248