3 * Normal-basis translation for binary fields
5 * (c) 2004 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
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.
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.
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,
28 /*----- Header files ------------------------------------------------------*/
33 /*----- Main code ---------------------------------------------------------*/
35 /* --- @gfn_copy@ --- *
37 * Arguments: @gfn *d@ = where to put the copy
38 * @const gfn *s@ = where the source is
42 * Use: Makes a copy of a translation matrix.
45 void gfn_copy(gfn *d, const gfn *s)
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]);
55 /* --- @gfn_destroy@ --- *
57 * Arguments: @gfn *m@ = a transformation matrix to free
61 * Use: Frees up a transformation matrix when it's no longer wanted.
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); }
67 /* --- @gfn_identity@ --- *
69 * Arguments: @gfn *m@ = where to put the matrix
70 * @size_t n@ = size of the matrix
74 * Use: Fills @m@ with an identity matrix.
77 void gfn_identity(gfn *m, size_t n)
82 m->r = xmalloc(n * sizeof(mp *));
84 for (i = 1; i < n; i++)
85 m->r[i] = mp_lsl(MP_NEW, m->r[i - 1], 1);
88 /* --- @gfn_invert@ --- *
90 * Arguments: @gfn *m@ = a transformation matrix
92 * Returns: Zero if successful, nonzero if the matrix was singular.
94 * Use: Inverts a transformation matrix.
97 int gfn_invert(gfn *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))
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;
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]);
131 /* --- @gfn_transform@ --- *
133 * Arguments: @gfn *m@ = conversion matrix to apply
134 * @mp *d@ = destination pointer
135 * @mp *x@ = input value
137 * Returns: The transformed element.
139 * Use: Transforms a field element according to the given matrix.
142 mp *gfn_transform(gfn *m, mp *d, mp *x)
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]);
154 /* --- @gfn_create@ --- *
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
162 * Returns: Zero if it worked, nonzero otherwise (e.g., if %$\beta$%
163 * doesn't generate a proper basis).
165 * Use: Constructs conversion matrices between polynomial and normal
166 * basis representations of binary field elements.
169 int gfn_create(mp *p, mp *beta, gfn *ntop, gfn *pton)
171 size_t m = mp_bits(p) - 1;
176 /* --- We start by building the the @ntop@ matrix --- *
178 * For mad reasons, the string representation of normal-basis elements is
182 gfreduce_create(&gr, p);
183 np = ntop ? ntop : &tmp;
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);
191 gfreduce_destroy(&gr);
193 /* --- That was easy -- now invert it --- */
196 if (ntop) gfn_copy(pton, np); else *pton = *np;
197 if (gfn_invert(pton)) {
199 if (ntop) gfn_destroy(ntop);
204 /* --- And we're done --- */
209 /*----- Test rig ----------------------------------------------------------*/
213 static int check(dstr *v)
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;
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])) {
230 fprintf(stderr, "*** inverse pton->ntop check failed (row %lu)\n",
232 MP_EPRINTX("*** p", p); MP_EPRINTX("*** beta", beta);
233 MP_EPRINTX("*** computed", y);
237 y = gfn_transform(&pton, y, xp);
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);
245 y = gfn_transform(&ntop, y, xn);
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);
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);
259 static test_chunk tests[] = {
260 { "gfn", check, { &type_mp, &type_mp, &type_mp, &type_mp } },
264 int main(int argc, char *argv[])
266 test_run(argc, argv, tests, SRCDIR "/t/gfn");
272 /*----- That's all, folks -------------------------------------------------*/