chiark - git - mdw - catacomb/blob - math/gfn.c

   1 /* -*-c-*-
   2  *
   3  * Normal-basis translation for binary fields
   4  *
   5  * (c) 2004 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   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.
  16  *
  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.
  21  *
  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
  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 {
 266   test_run(argc, argv, tests, SRCDIR "/t/gfn");
 267   return (0);
 268 }
 269
 270 #endif
 271
 272 /*----- That's all, folks -------------------------------------------------*/