M4RIE 20250128
Loading...
Searching...
No Matches
mzd_poly.h
Go to the documentation of this file.
1
8
9#ifndef M4RIE_MZD_POLY_H
10#define M4RIE_MZD_POLY_H
11
12/******************************************************************************
13*
14* M4RIE: Linear Algebra over GF(2^e)
15*
16* Copyright (C) 2011 Martin Albrecht <martinralbrecht@googlemail.com>
17*
18* Distributed under the terms of the GNU General Public License (GEL)
19* version 2 or higher.
20*
21* This code is distributed in the hope that it will be useful,
22* but WITHOUT ANY WARRANTY; without even the implied warranty of
23* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
24* General Public License for more details.
25*
26* The full text of the GPL is available at:
27*
28* http://www.gnu.org/licenses/
29******************************************************************************/
30
31#include <m4ri/m4ri.h>
32#include "mzd_ptr.h"
33#include "gf2x.h"
34#include "blm.h"
35
39
40typedef struct {
41 mzd_t **x;
42 rci_t nrows;
43 rci_t ncols;
46
59
60static inline mzd_poly_t *_mzd_poly_add(mzd_poly_t *C, const mzd_poly_t *A, const mzd_poly_t *B, unsigned int offset) {
61 _mzd_ptr_add(C->x+offset, (const mzd_t**)A->x, (const mzd_t**)B->x, A->depth);
62 return C;
63}
64
74
75static inline mzd_poly_t *mzd_poly_add(mzd_poly_t *C, const mzd_poly_t *A, const mzd_poly_t *B) {
76 assert(C->depth >= A->depth && A->depth == B->depth);
77 return _mzd_poly_add(C, A, B, 0);
78}
79
89
90static inline mzd_poly_t *mzd_poly_init(const deg_t d, const rci_t m, const rci_t n) {
91 mzd_poly_t *A = (mzd_poly_t*)m4ri_mm_malloc(sizeof(mzd_poly_t));
92 A->x = (mzd_t**)m4ri_mm_malloc(sizeof(mzd_t*)*(d+1));
93
94 A->nrows = m;
95 A->ncols = n;
96 A->depth = d+1;
97
98 for(int i=0; i<A->depth; i++)
99 A->x[i] = mzd_init(m,n);
100 return A;
101}
102
110
111static inline void mzd_poly_free(mzd_poly_t *A) {
112 for(int i=0; i<A->depth; i++)
113 mzd_free(A->x[i]);
114 m4ri_mm_free(A->x);
115 m4ri_mm_free(A);
116}
117
126
127static inline mzd_poly_t *_mzd_poly_adapt_depth(mzd_poly_t *A, const deg_t new_depth) {
128 if (new_depth < A->depth) {
129 for(int i=new_depth; i<A->depth; i++) {
130 mzd_free(A->x[i]);
131 A->x[i] = NULL;
132 }
133 } else {
134 for(int i=A->depth; i<new_depth; i++) {
135 A->x[i] = mzd_init(A->nrows,A->ncols);
136 }
137 }
138 A->depth = new_depth;
139 return A;
140}
141
151
152static inline mzd_poly_t *_mzd_poly_addmul_naive(mzd_poly_t *C, const mzd_poly_t *A, const mzd_poly_t *B) {
153 if (C == NULL)
154 C = mzd_poly_init(A->depth+B->depth-1, A->nrows, B->ncols);
155
156 for(int i=0; i<A->depth; i++) {
157 for(int j=0; j<B->depth; j++) {
158 mzd_addmul(C->x[i+j], A->x[i], B->x[j], 0);
159 }
160 }
161 return C;
162}
163
173
174
176 assert(A->depth == B->depth);
177
178 if (C == NULL)
179 C = mzd_poly_init(A->depth+B->depth-1, A->nrows, B->ncols);
180 switch(A->depth) {
181 case 0:
182 m4ri_die("depth 0: seriously?");
183 case 1: mzd_addmul(C->x[0], A->x[0], B->x[0], 0); break;
184 case 2: _mzd_ptr_addmul_karatsuba2(NULL, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
185 case 3: _mzd_ptr_addmul_karatsuba3(NULL, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
186 case 4: _mzd_ptr_addmul_karatsuba4(NULL, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
187 case 5: _mzd_ptr_addmul_karatsuba5(NULL, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
188 case 6: _mzd_ptr_addmul_karatsuba6(NULL, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
189 case 7: _mzd_ptr_addmul_karatsuba7(NULL, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
190 case 8: _mzd_ptr_addmul_karatsuba8(NULL, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
191 case 9: _mzd_ptr_addmul_karatsuba9(NULL, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
192 case 10: _mzd_ptr_addmul_karatsuba10(NULL, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
193 case 11: _mzd_ptr_addmul_karatsuba11(NULL, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
194 case 12: _mzd_ptr_addmul_karatsuba12(NULL, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
195 case 13: _mzd_ptr_addmul_karatsuba13(NULL, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
196 case 14: _mzd_ptr_addmul_karatsuba14(NULL, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
197 case 15: _mzd_ptr_addmul_karatsuba15(NULL, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
198 case 16: _mzd_ptr_addmul_karatsuba16(NULL, C->x, (const mzd_t**)A->x, (const mzd_t**)B->x); break;
199 default:
200 m4ri_die("Not implemented\n");
201 }
202 return C;
203}
204
208
210 assert(f!=NULL);
211 assert(f->F->ncols == A->depth && f->G->ncols == B->depth);
212
213 if (C == NULL)
214 C = mzd_poly_init(A->depth+B->depth-1, A->nrows, B->ncols);
215
216 _mzd_ptr_apply_blm(C->x, (const mzd_t**)A->x, (const mzd_t**)B->x, f);
217 return C;
218}
219
220
224
226 int *p = crt_init(A->depth, B->depth);
227 blm_t *f = blm_init_crt(NULL, A->depth, B->depth, p, 1);
228 _mzd_poly_addmul_blm(C, A, B, f);
229 blm_free(f);
230 m4ri_mm_free(p);
231 return C;
232}
233
237
239
251
252static inline int mzd_poly_cmp(mzd_poly_t *A, mzd_poly_t *B) {
253 int r = 0;
254 if ((A->depth != B->depth) ) {
255 if (A->depth < B->depth)
256 return -1;
257 else
258 return 1;
259 }
260 for(int i=0; i<A->depth; i++)
261 r |= mzd_cmp(A->x[i],B->x[i]);
262 return r;
263}
264
274
275static inline void mzd_poly_randomize(mzd_poly_t *A) {
276 for(int i=0; i<A->depth; i++)
277 mzd_randomize(A->x[i]);
278}
279
280#endif //M4RIE_MZD_POLY_H
Bilinear Maps on Matrices over GF(2).
static void _mzd_ptr_apply_blm(mzd_t **X, const mzd_t **A, const mzd_t **B, const blm_t *f)
Apply f on A and B, writing to X.
Definition blm.h:153
for degrees < 64
int deg_t
Definition gf2x.h:37
static mzd_poly_t * _mzd_poly_add(mzd_poly_t *C, const mzd_poly_t *A, const mzd_poly_t *B, unsigned int offset)
C += (A+B)*x^offset.
Definition mzd_poly.h:60
static mzd_poly_t * mzd_poly_add(mzd_poly_t *C, const mzd_poly_t *A, const mzd_poly_t *B)
C += (A+B)
Definition mzd_poly.h:75
static void mzd_poly_randomize(mzd_poly_t *A)
Fill matrix A with random elements.
Definition mzd_poly.h:275
static mzd_poly_t * mzd_poly_init(const deg_t d, const rci_t m, const rci_t n)
Create a new polynomial of degree d with m x n matrices as coefficients.
Definition mzd_poly.h:90
static void mzd_poly_free(mzd_poly_t *A)
Free polynomial A.
Definition mzd_poly.h:111
static mzd_poly_t * _mzd_poly_adapt_depth(mzd_poly_t *A, const deg_t new_depth)
change depth of A to new_depth.
Definition mzd_poly.h:127
void _mzd_ptr_addmul_karatsuba2(const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B)
over using 3 multiplications over and 2 temporary matrices.
Definition karatsuba.c:4
static mzd_poly_t * _mzd_poly_addmul_karatsubs_balanced(mzd_poly_t *C, const mzd_poly_t *A, const mzd_poly_t *B)
C += A*B using Karatsuba multiplication on balanced inputs.
Definition mzd_poly.h:175
static mzd_poly_t * _mzd_poly_addmul_naive(mzd_poly_t *C, const mzd_poly_t *A, const mzd_poly_t *B)
C += A*B using naive polynomial multiplication.
Definition mzd_poly.h:152
static int mzd_poly_cmp(mzd_poly_t *A, mzd_poly_t *B)
Return -1,0,1 if if A < B, A == B or A > B respectively.
Definition mzd_poly.h:252
mzd_poly_t * _mzd_poly_addmul_ext1(mzd_poly_t *C, mzd_poly_t *A, mzd_poly_t *B)
C += A*B using arithmetic in GF(2^log2(d)) if C has degree d.
Definition mzd_poly.c:12
static mzd_poly_t * _mzd_poly_addmul_blm(mzd_poly_t *C, mzd_poly_t *A, mzd_poly_t *B, const blm_t *f)
C += A*B by applying the bilinear maps f, i.e. f->H*((f->F*A) x (f->G*B)).
Definition mzd_poly.h:209
static mzd_poly_t * _mzd_poly_addmul_crt(mzd_poly_t *C, mzd_poly_t *A, mzd_poly_t *B)
C += A*B using the Chinese Remainder Theorem.
Definition mzd_poly.h:225
Bilinear Maps on Matrices over GF(2).
Definition blm.h:51
mzd_t * G
Definition blm.h:58
mzd_t * F
Definition blm.h:55
will be the data type for matrices over [x] in the future
Definition mzd_poly.h:40
rci_t ncols
Definition mzd_poly.h:43
deg_t depth
Definition mzd_poly.h:44
rci_t nrows
Definition mzd_poly.h:42
mzd_t ** x
Definition mzd_poly.h:41