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

   1 /* -*-c-*-
   2  *
   3  * $Id: gfn.c,v 1.1 2004/04/01 21:28:41 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 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: gfn.c,v $
  33  * Revision 1.1  2004/04/01 21:28:41  mdw
  34  * Normal basis support (translates to poly basis internally).  Rewrite
  35  * EC and prime group table generators in awk, so that they can reuse data
  36  * for repeated constants.
  37  *
  38  */
  39
  40 /*----- Header files ------------------------------------------------------*/
  41
  42 #include "gfreduce.h"
  43 #include "gfn.h"
  44
  45 /*----- Main code ---------------------------------------------------------*/
  46
  47 /* --- @gfn_copy@ --- *
  48  *
  49  * Arguments:   @gfn *d@ = where to put the copy
  50  *              @const gfn *s@ = where the source is
  51  *
  52  * Returns:     ---
  53  *
  54  * Use:         Makes a copy of a translation matrix.
  55  */
  56
  57 void gfn_copy(gfn *d, const gfn *s)
  58 {
  59   size_t i;
  60
  61   d->n = s->n;
  62   d->r = xmalloc(s->n * sizeof(mp *));
  63   for (i = 0; i < s->n; i++)
  64     d->r[i] = MP_COPY(s->r[i]);
  65 }
  66
  67 /* --- @gfn_destroy@ --- *
  68  *
  69  * Arguments:   @gfn *m@ = a transformation matrix to free
  70  *
  71  * Returns:     ---
  72  *
  73  * Use:         Frees up a transformation matrix when it's no longer wanted.
  74  */
  75
  76 void gfn_destroy(gfn *m)
  77   { size_t i; for (i = 0; i < m->n; i++) MP_DROP(m->r[i]); xfree(m->r); }
  78
  79 /* --- @gfn_identity@ --- *
  80  *
  81  * Arguments:   @gfn *m@ = where to put the matrix
  82  *              @size_t n@ = size of the matrix
  83  *
  84  * Returns:     ---
  85  *
  86  * Use:         Fills @m@ with an identity matrix.
  87  */
  88
  89 void gfn_identity(gfn *m, size_t n)
  90 {
  91   size_t i;
  92
  93   m->n = n;
  94   m->r = xmalloc(n * sizeof(mp *));
  95   m->r[0] = MP_ONE;
  96   for (i = 1; i < n; i++)
  97     m->r[i] = mp_lsl(MP_NEW, m->r[i - 1], 1);
  98 }
  99
 100 /* --- @gfn_invert@ --- *
 101  *
 102  * Arguments:   @gfn *m@ = a transformation matrix
 103  *
 104  * Returns:     Zero if successful, nonzero if the matrix was singular.
 105  *
 106  * Use:         Inverts a transformation matrix.
 107  */
 108
 109 int gfn_invert(gfn *m)
 110 {
 111   size_t i, j;
 112   gfn mm;
 113   mp *t;
 114   int rc = -1;
 115
 116   mm = *m;
 117   gfn_identity(m, mm.n);
 118   for (i = 0; i < mm.n; i++) {
 119     if (!mp_testbit(mm.r[i], i)) {
 120       for (j = i + 1; j < mm.n; j++) {
 121         if (mp_testbit(mm.r[j], i))
 122           goto found_set;
 123       }
 124       goto fail;
 125     found_set:
 126       t = mm.r[i]; mm.r[i] = mm.r[j]; mm.r[j] = t;
 127       t = m->r[i]; m->r[i] = m->r[j]; m->r[j] = t;
 128     }
 129     for (j = 0; j < mm.n; j++) {
 130       if (j == i) continue;
 131       if (mp_testbit(mm.r[j], i)) {
 132         mm.r[j] = mp_xor(mm.r[j], mm.r[j], mm.r[i]);
 133         m->r[j] = mp_xor(m->r[j], m->r[j], m->r[i]);
 134       }
 135     }
 136   }
 137   rc = 0;
 138 fail:
 139   gfn_destroy(&mm);
 140   return (rc);
 141 }
 142
 143 /* --- @gfn_transform@ --- *
 144  *
 145  * Arguments:   @gfn *m@ = conversion matrix to apply
 146  *              @mp *d@ = destination pointer
 147  *              @mp *x@ = input value
 148  *
 149  * Returns:     The transformed element.
 150  *
 151  * Use:         Transforms a field element according to the given matrix.
 152  */
 153
 154 mp *gfn_transform(gfn *m, mp *d, mp *x)
 155 {
 156   mp *y = MP_ZERO;
 157   size_t i;
 158   mpscan sc;
 159
 160   for (i = 0, mp_scan(&sc, x); i < m->n && mp_step(&sc); i++)
 161     if (mp_bit(&sc)) y = mp_xor(y, y, m->r[i]);
 162   mp_drop(d);
 163   return (y);
 164 }
 165
 166 /* --- @gfn_create@ --- *
 167  *
 168  * Arguments:   @mp *p@ = modulus for polynomial basis
 169  *              @mp *beta@ = the generator of the normal basis, expressed
 170  *                      relative to the polynomial basis
 171  *              @gfn *ntop@ = output normal-to-polynomail conversion matrix
 172  *              @gfn *pton@ = output polynomial-to-normal conversion matrix
 173  *
 174  * Returns:     Zero if it worked, nonzero otherwise (e.g., if %$\beta$%
 175  *              doesn't generate a proper basis).
 176  *
 177  * Use:         Constructs conversion matrices between polynomial and normal
 178  *              basis representations of binary field elements.
 179  */
 180
 181 int gfn_create(mp *p, mp *beta, gfn *ntop, gfn *pton)
 182 {
 183   size_t m = mp_bits(p) - 1;
 184   size_t i;
 185   gfreduce gr;
 186   gfn *np, tmp;
 187
 188   /* --- We start by building the the @ntop@ matrix --- *
 189    *
 190    * For mad reasons, the string representation of normal-basis elements is
 191    * backwards.
 192    */
 193
 194   gfreduce_create(&gr, p);
 195   np = ntop ? ntop : &tmp;
 196   np->n = m;
 197   np->r = xmalloc(m * sizeof(mp *));
 198   np->r[m - 1] = MP_COPY(beta);
 199   for (i = m - 1; i--; ) {
 200     mp *x = gf_sqr(MP_NEW, np->r[i + 1]);
 201     np->r[i] = gfreduce_do(&gr, x, x);
 202   }
 203   gfreduce_destroy(&gr);
 204
 205   /* --- That was easy -- now invert it --- */
 206
 207   if (pton) {
 208     if (ntop) gfn_copy(pton, np); else *pton = *np;
 209     if (gfn_invert(pton)) {
 210       gfn_destroy(pton);
 211       if (ntop) gfn_destroy(ntop);
 212       return (-1);
 213     }
 214   }
 215
 216   /* --- And we're done --- */
 217
 218   return (0);
 219 }
 220
 221 /*----- Test rig ----------------------------------------------------------*/
 222
 223 #ifdef TEST_RIG
 224
 225 static int check(dstr *v)
 226 {
 227   mp *p = *(mp **)v[0].buf;
 228   mp *beta = *(mp **)v[1].buf;
 229   mp *xp = *(mp **)v[2].buf;
 230   mp *xn = *(mp **)v[3].buf;
 231   mp *y = MP_NEW;
 232   gfn pton, ntop, ii;
 233   size_t i;
 234   int ok = 1;
 235
 236   gfn_create(p, beta, &ntop, &pton);
 237   gfn_identity(&ii, pton.n);
 238   for (i = 0; i < pton.n; i++) {
 239     y = gfn_transform(&ntop, y, pton.r[i]);
 240     if (!MP_EQ(y, ii.r[i])) {
 241       ok = 0;
 242       fprintf(stderr, "*** inverse pton->ntop check failed (row %lu)\n",
 243               (unsigned long)i);
 244       MP_EPRINTX("*** p", p); MP_EPRINTX("*** beta", beta);
 245       MP_EPRINTX("*** computed", y);
 246     }
 247   }
 248   gfn_destroy(&ii);
 249   y = gfn_transform(&pton, y, xp);
 250   if (!MP_EQ(y, xn)) {
 251     ok = 0;
 252     fprintf(stderr, "*** pton failed\n");
 253     MP_EPRINTX("*** p", p); MP_EPRINTX("*** beta", beta);
 254     MP_EPRINTX("*** xp", xp); MP_EPRINTX("*** xn", xn);
 255     MP_EPRINTX("*** computed", y);
 256   }
 257   y = gfn_transform(&ntop, y, xn);
 258   if (!MP_EQ(y, xp)) {
 259     ok = 0;
 260     fprintf(stderr, "*** ntop failed\n");
 261     MP_EPRINTX("*** p", p); MP_EPRINTX("*** beta", beta);
 262     MP_EPRINTX("*** xp", xp); MP_EPRINTX("*** xn", xn);
 263     MP_EPRINTX("*** computed", y);
 264   }
 265   gfn_destroy(&pton); gfn_destroy(&ntop);
 266   mp_drop(p); mp_drop(beta); mp_drop(xp); mp_drop(xn); mp_drop(y);
 267   assert(mparena_count(MPARENA_GLOBAL) == 0);
 268   return (ok);
 269 }
 270
 271 static test_chunk tests[] = {
 272   { "gfn", check, { &type_mp, &type_mp, &type_mp, &type_mp } },
 273   { 0 }
 274 };
 275
 276 int main(int argc, char *argv[])
 277 {
 278   test_run(argc, argv, tests, SRCDIR "/tests/gfn");
 279   return (0);
 280 }
 281
 282 #endif
 283
 284 /*----- That's all, folks -------------------------------------------------*/