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

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