1 /**
2 * \file blm.h
3 *
4 * \brief Bilinear Maps on Matrices over GF(2).
5 *
6 * This is used to realise mzd_poly_t multiplication.
7 *
8 * \author Martin Albrecht <martinralbrecht@googlemail.com>
9 */
10
11 #ifndef M4RIE_BLM_H
12 #define M4RIE_BLM_H
13
14 /******************************************************************************
15 *
16 * M4RIE: Linear Algebra over GF(2^e)
17 *
18 * Copyright (C) 2013 Martin Albrecht <martinralbrecht@googlemail.com>
19 *
20 * Distributed under the terms of the GNU General Public License (GEL)
21 * version 2 or higher.
22 *
23 * This code is distributed in the hope that it will be useful,
24 * but WITHOUT ANY WARRANTY; without even the implied warranty of
25 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
26 * General Public License for more details.
27 *
28 * The full text of the GPL is available at:
29 *
30 * http://www.gnu.org/licenses/
31 ******************************************************************************/
32
33 #include <m4ri/m4ri.h>
34 #include "m4rie/gf2e.h"
35
36 /**
37 * \brief We consider at most polynomials of degree M4RIE_MAX_DEGREE in CRT.
38 */
39
40 #define M4RIE_CRT_LEN (M4RIE_MAX_DEGREE + 1)
41
42 /**
43 * \brief Bilinear Maps on Matrices over GF(2).
44 *
45 * Encodes the bilinear map H*((F*A) x (G*B)) where A,B are vectors of mzd_t, "*" is matrix-vector
46 * multiplication and "x" is pointwise multiplication.
47 *
48 * If a DJB map is not NULL, it will be used instead its matrix representant.
49 */
50
51 typedef struct {
52 mzd_t *H; /*!< final linear map H*/
53 djb_t *h; /*!< final linear map H (DJB encoding)*/
54
55 mzd_t *F; /*!< lineatr map on A */
56 djb_t *f; /*!< lineatr map on N (DJB encoding) */
57
58 mzd_t *G; /*!< lineatr map on B */
59 djb_t *g; /*!< lineatr map on B (DJB encoding) */
60 } blm_t;
61
62 /**
63 * costs[i] = cost of multiplying two polynomials of length i over \GF2.
64 */
65
66 extern const int costs[17];
67
68 /**
69 * Return the multiplication cost of the multiplication scheme p
70 */
71
blm_cost_crt(const int p[M4RIE_CRT_LEN])72 static inline int blm_cost_crt(const int p[M4RIE_CRT_LEN]) {
73 int cost = costs[p[0]];
74 for(deg_t d=1; d<M4RIE_CRT_LEN; d++)
75 cost += costs[d] * p[d];
76 return cost;
77 }
78
79 /**
80 * Find a list of co-prime polynomials p_i such that deg(prod(p_i)) >= f_len*g_len-1.
81 *
82 * We store the number of polynomials of degree d in p[d]. We store the degree w of (x-infinity)^w
83 * in p[0].
84 */
85
86 int *crt_init(const deg_t f_len, const deg_t g_len);
87
88 /**
89 * Compute H, F, G such that vec(c) = H*(F*vec(a) x G*vec(b))
90 * with poly(c) = poly(a)*poly(b),
91 * deg(poly(a)) = a_ncols -1, deg(poly(b)) = b_ncols -1 and "x" being pointwise multiplication
92 *
93 * This is realised by a multi-modular computation modulo the primes up to degree deg (which may not
94 * be irreducible polynomials, but merely co-prime).
95 */
96
97 blm_t *blm_init_crt(const gf2e *ff, const deg_t f_ncols, const deg_t g_ncols, const int *p, int djb);
98
99 /**
100 * Given F and G compute H.
101 *
102 * \param ff finite field for modular reduction
103 * \param f Bilinear Map with F and G already computed.
104 */
105
106 blm_t *_blm_finish_polymult(const gf2e *ff, blm_t *f);
107
108 /**
109 * Free bilinear map f.
110 */
111
112 void blm_free(blm_t *f);
113
114 /**
115 * \brief Compile DJB map for f
116 *
117 * \param f Bilinear map
118 */
119
120 blm_t *_blm_djb_compile(blm_t *f);
121
122 /**
123 * \brief Apply f (stored as a matrix) on A and B, writing to X
124 *
125 * \param X Array of matrices
126 * \param A Array of matrices
127 * \param B Array of matrices
128 * \param f Bilinear map
129 */
130
131 void _mzd_ptr_apply_blm_mzd(mzd_t **X, const mzd_t **A, const mzd_t **B, const blm_t *f);
132
133 /**
134 * \brief Apply f (stored as a DJB map) on A and B, writing to X
135 *
136 * \param X Array of matrices
137 * \param A Array of matrices
138 * \param B Array of matrices
139 * \param f Bilinear map
140 */
141
142 void _mzd_ptr_apply_blm_djb(mzd_t **X, const mzd_t **A, const mzd_t **B, const blm_t *f);
143
144 /**
145 * \brief Apply f on A and B, writing to X
146 *
147 * \param X Array of matrices
148 * \param A Array of matrices
149 * \param B Array of matrices
150 * \param f Bilinear map
151 */
152
_mzd_ptr_apply_blm(mzd_t ** X,const mzd_t ** A,const mzd_t ** B,const blm_t * f)153 static inline void _mzd_ptr_apply_blm(mzd_t **X, const mzd_t **A, const mzd_t **B, const blm_t *f) {
154 if (f->f!=NULL)
155 _mzd_ptr_apply_blm_djb(X, A, B, f);
156 else
157 _mzd_ptr_apply_blm_mzd(X, A, B, f);
158 }
159
160
161 #endif //M4RIE_BLM_H
162