4edc47b8 |
1 | /* -*-c-*- |
4edc47b8 |
2 | * |
3 | * Normal-basis translation for binary fields |
4 | * |
5 | * (c) 2004 Straylight/Edgeware |
6 | */ |
7 | |
45c0fd36 |
8 | /*----- Licensing notice --------------------------------------------------* |
4edc47b8 |
9 | * |
10 | * This file is part of Catacomb. |
11 | * |
12 | * Catacomb is free software; you can redistribute it and/or modify |
13 | * it under the terms of the GNU Library General Public License as |
14 | * published by the Free Software Foundation; either version 2 of the |
15 | * License, or (at your option) any later version. |
45c0fd36 |
16 | * |
4edc47b8 |
17 | * Catacomb is distributed in the hope that it will be useful, |
18 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
19 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
20 | * GNU Library General Public License for more details. |
45c0fd36 |
21 | * |
4edc47b8 |
22 | * You should have received a copy of the GNU Library General Public |
23 | * License along with Catacomb; if not, write to the Free |
24 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, |
25 | * MA 02111-1307, USA. |
26 | */ |
27 | |
4edc47b8 |
28 | /*----- Header files ------------------------------------------------------*/ |
29 | |
30 | #include "gfreduce.h" |
31 | #include "gfn.h" |
32 | |
33 | /*----- Main code ---------------------------------------------------------*/ |
34 | |
35 | /* --- @gfn_copy@ --- * |
36 | * |
37 | * Arguments: @gfn *d@ = where to put the copy |
38 | * @const gfn *s@ = where the source is |
39 | * |
40 | * Returns: --- |
41 | * |
42 | * Use: Makes a copy of a translation matrix. |
43 | */ |
44 | |
45 | void gfn_copy(gfn *d, const gfn *s) |
46 | { |
47 | size_t i; |
48 | |
49 | d->n = s->n; |
50 | d->r = xmalloc(s->n * sizeof(mp *)); |
51 | for (i = 0; i < s->n; i++) |
52 | d->r[i] = MP_COPY(s->r[i]); |
53 | } |
54 | |
55 | /* --- @gfn_destroy@ --- * |
56 | * |
57 | * Arguments: @gfn *m@ = a transformation matrix to free |
58 | * |
59 | * Returns: --- |
60 | * |
61 | * Use: Frees up a transformation matrix when it's no longer wanted. |
62 | */ |
63 | |
64 | void gfn_destroy(gfn *m) |
65 | { size_t i; for (i = 0; i < m->n; i++) MP_DROP(m->r[i]); xfree(m->r); } |
66 | |
67 | /* --- @gfn_identity@ --- * |
68 | * |
69 | * Arguments: @gfn *m@ = where to put the matrix |
70 | * @size_t n@ = size of the matrix |
71 | * |
72 | * Returns: --- |
73 | * |
74 | * Use: Fills @m@ with an identity matrix. |
75 | */ |
76 | |
77 | void gfn_identity(gfn *m, size_t n) |
78 | { |
79 | size_t i; |
80 | |
81 | m->n = n; |
82 | m->r = xmalloc(n * sizeof(mp *)); |
83 | m->r[0] = MP_ONE; |
84 | for (i = 1; i < n; i++) |
85 | m->r[i] = mp_lsl(MP_NEW, m->r[i - 1], 1); |
86 | } |
87 | |
88 | /* --- @gfn_invert@ --- * |
89 | * |
90 | * Arguments: @gfn *m@ = a transformation matrix |
91 | * |
92 | * Returns: Zero if successful, nonzero if the matrix was singular. |
93 | * |
94 | * Use: Inverts a transformation matrix. |
95 | */ |
96 | |
97 | int gfn_invert(gfn *m) |
98 | { |
99 | size_t i, j; |
100 | gfn mm; |
101 | mp *t; |
102 | int rc = -1; |
103 | |
104 | mm = *m; |
105 | gfn_identity(m, mm.n); |
106 | for (i = 0; i < mm.n; i++) { |
107 | if (!mp_testbit(mm.r[i], i)) { |
108 | for (j = i + 1; j < mm.n; j++) { |
109 | if (mp_testbit(mm.r[j], i)) |
110 | goto found_set; |
111 | } |
112 | goto fail; |
113 | found_set: |
114 | t = mm.r[i]; mm.r[i] = mm.r[j]; mm.r[j] = t; |
115 | t = m->r[i]; m->r[i] = m->r[j]; m->r[j] = t; |
116 | } |
117 | for (j = 0; j < mm.n; j++) { |
118 | if (j == i) continue; |
119 | if (mp_testbit(mm.r[j], i)) { |
120 | mm.r[j] = mp_xor(mm.r[j], mm.r[j], mm.r[i]); |
121 | m->r[j] = mp_xor(m->r[j], m->r[j], m->r[i]); |
122 | } |
123 | } |
124 | } |
125 | rc = 0; |
126 | fail: |
127 | gfn_destroy(&mm); |
128 | return (rc); |
129 | } |
130 | |
131 | /* --- @gfn_transform@ --- * |
132 | * |
133 | * Arguments: @gfn *m@ = conversion matrix to apply |
134 | * @mp *d@ = destination pointer |
135 | * @mp *x@ = input value |
136 | * |
137 | * Returns: The transformed element. |
138 | * |
139 | * Use: Transforms a field element according to the given matrix. |
140 | */ |
141 | |
142 | mp *gfn_transform(gfn *m, mp *d, mp *x) |
143 | { |
144 | mp *y = MP_ZERO; |
145 | size_t i; |
146 | mpscan sc; |
147 | |
148 | for (i = 0, mp_scan(&sc, x); i < m->n && mp_step(&sc); i++) |
149 | if (mp_bit(&sc)) y = mp_xor(y, y, m->r[i]); |
150 | mp_drop(d); |
151 | return (y); |
152 | } |
153 | |
154 | /* --- @gfn_create@ --- * |
155 | * |
156 | * Arguments: @mp *p@ = modulus for polynomial basis |
157 | * @mp *beta@ = the generator of the normal basis, expressed |
158 | * relative to the polynomial basis |
159 | * @gfn *ntop@ = output normal-to-polynomail conversion matrix |
160 | * @gfn *pton@ = output polynomial-to-normal conversion matrix |
161 | * |
162 | * Returns: Zero if it worked, nonzero otherwise (e.g., if %$\beta$% |
163 | * doesn't generate a proper basis). |
164 | * |
165 | * Use: Constructs conversion matrices between polynomial and normal |
166 | * basis representations of binary field elements. |
167 | */ |
168 | |
169 | int gfn_create(mp *p, mp *beta, gfn *ntop, gfn *pton) |
170 | { |
171 | size_t m = mp_bits(p) - 1; |
172 | size_t i; |
173 | gfreduce gr; |
174 | gfn *np, tmp; |
175 | |
176 | /* --- We start by building the the @ntop@ matrix --- * |
177 | * |
178 | * For mad reasons, the string representation of normal-basis elements is |
179 | * backwards. |
180 | */ |
181 | |
182 | gfreduce_create(&gr, p); |
183 | np = ntop ? ntop : &tmp; |
184 | np->n = m; |
185 | np->r = xmalloc(m * sizeof(mp *)); |
186 | np->r[m - 1] = MP_COPY(beta); |
187 | for (i = m - 1; i--; ) { |
188 | mp *x = gf_sqr(MP_NEW, np->r[i + 1]); |
189 | np->r[i] = gfreduce_do(&gr, x, x); |
190 | } |
191 | gfreduce_destroy(&gr); |
192 | |
193 | /* --- That was easy -- now invert it --- */ |
194 | |
195 | if (pton) { |
196 | if (ntop) gfn_copy(pton, np); else *pton = *np; |
197 | if (gfn_invert(pton)) { |
198 | gfn_destroy(pton); |
199 | if (ntop) gfn_destroy(ntop); |
200 | return (-1); |
201 | } |
202 | } |
203 | |
204 | /* --- And we're done --- */ |
205 | |
206 | return (0); |
207 | } |
208 | |
209 | /*----- Test rig ----------------------------------------------------------*/ |
210 | |
211 | #ifdef TEST_RIG |
212 | |
213 | static int check(dstr *v) |
214 | { |
215 | mp *p = *(mp **)v[0].buf; |
216 | mp *beta = *(mp **)v[1].buf; |
217 | mp *xp = *(mp **)v[2].buf; |
218 | mp *xn = *(mp **)v[3].buf; |
219 | mp *y = MP_NEW; |
220 | gfn pton, ntop, ii; |
221 | size_t i; |
222 | int ok = 1; |
223 | |
224 | gfn_create(p, beta, &ntop, &pton); |
225 | gfn_identity(&ii, pton.n); |
226 | for (i = 0; i < pton.n; i++) { |
227 | y = gfn_transform(&ntop, y, pton.r[i]); |
228 | if (!MP_EQ(y, ii.r[i])) { |
229 | ok = 0; |
230 | fprintf(stderr, "*** inverse pton->ntop check failed (row %lu)\n", |
231 | (unsigned long)i); |
232 | MP_EPRINTX("*** p", p); MP_EPRINTX("*** beta", beta); |
233 | MP_EPRINTX("*** computed", y); |
234 | } |
235 | } |
236 | gfn_destroy(&ii); |
237 | y = gfn_transform(&pton, y, xp); |
238 | if (!MP_EQ(y, xn)) { |
239 | ok = 0; |
240 | fprintf(stderr, "*** pton failed\n"); |
241 | MP_EPRINTX("*** p", p); MP_EPRINTX("*** beta", beta); |
242 | MP_EPRINTX("*** xp", xp); MP_EPRINTX("*** xn", xn); |
243 | MP_EPRINTX("*** computed", y); |
244 | } |
245 | y = gfn_transform(&ntop, y, xn); |
246 | if (!MP_EQ(y, xp)) { |
247 | ok = 0; |
248 | fprintf(stderr, "*** ntop failed\n"); |
249 | MP_EPRINTX("*** p", p); MP_EPRINTX("*** beta", beta); |
250 | MP_EPRINTX("*** xp", xp); MP_EPRINTX("*** xn", xn); |
251 | MP_EPRINTX("*** computed", y); |
252 | } |
253 | gfn_destroy(&pton); gfn_destroy(&ntop); |
254 | mp_drop(p); mp_drop(beta); mp_drop(xp); mp_drop(xn); mp_drop(y); |
255 | assert(mparena_count(MPARENA_GLOBAL) == 0); |
256 | return (ok); |
257 | } |
258 | |
259 | static test_chunk tests[] = { |
260 | { "gfn", check, { &type_mp, &type_mp, &type_mp, &type_mp } }, |
261 | { 0 } |
262 | }; |
263 | |
264 | int main(int argc, char *argv[]) |
265 | { |
0f00dc4c |
266 | test_run(argc, argv, tests, SRCDIR "/t/gfn"); |
4edc47b8 |
267 | return (0); |
268 | } |
269 | |
270 | #endif |
271 | |
272 | /*----- That's all, folks -------------------------------------------------*/ |