chiark / gitweb /
**/*.S: Arrange assembler preambles consistently.
[catacomb] / math / gfn.c
CommitLineData
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
45void 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
64void 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
77void 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
97int 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;
126fail:
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
142mp *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
169int 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
213static 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
259static test_chunk tests[] = {
260 { "gfn", check, { &type_mp, &type_mp, &type_mp, &type_mp } },
261 { 0 }
262};
263
264int 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 -------------------------------------------------*/