git.distorted.org.uk Git - u/mdw/catacomb/blob - calc/gfx.cal

   1 /* -*-apcalc-*-
   2  *
   3  * $Id: gfx.cal,v 1.2 2004/03/21 22:52:06 mdw Exp $
   4  *
   5  * Testbed for %$\gf{2}$% poltnomial arithmetic
   6  *
   7  * (c) 2000 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: gfx.cal,v $
  33  * Revision 1.2  2004/03/21 22:52:06  mdw
  34  * Merge and close elliptic curve branch.
  35  *
  36  * Revision 1.1.4.1  2004/03/21 22:39:46  mdw
  37  * Elliptic curves on binary fields work.
  38  *
  39  * Revision 1.1  2000/10/08 16:01:37  mdw
  40  * Prototypes of various bits of code.
  41  *
  42  */
  43
  44 /*----- Object types ------------------------------------------------------*/
  45
  46 obj gf { x };
  47
  48 /*----- Static variables --------------------------------------------------*/
  49
  50 static obj gf example_gf_object;
  51
  52 /*----- Main code ---------------------------------------------------------*/
  53
  54 dummy = config("lib_debug", -1);
  55
  56 define gf(x)
  57 {
  58   local obj gf g;
  59   g.x = x;
  60   return (g);
  61 }
  62
  63 define gfint(x)
  64 {
  65   if (istype(x, example_gf_object))
  66     return (x.x);
  67   else
  68     return (x);
  69 }
  70
  71 define gf_add(x, y) = gf(xor(gfint(x), gfint(y)));
  72 define gf_sub(x, y) = gf(xor(gfint(x), gfint(y)));
  73 define gf_neg(x) = x;
  74
  75 define gf_mul(x, y)
  76 {
  77   local a = gfint(x), b = gfint(y), z = 0, i, bits = highbit(a);
  78   for (i = 0; i <= bits; i++) {
  79     if (bit(a, i))
  80       z = xor(z, b << i);
  81   }
  82   return gf(z);
  83 }
  84
  85 define gfx_div(rx, dx)
  86 {
  87   local r = gfint(rx), d = gfint(dx), i;
  88   local q = 0, dbits, rbits;
  89   dbits = highbit(d);
  90   rbits = highbit(r);
  91   for (i = rbits - dbits; i >= 0; i--) {
  92     if (bit(r, i + dbits)) {
  93       r = xor(r, d << i);
  94       q |= (1 << i);
  95     }
  96   }
  97   return list(q, r);
  98 }
  99
 100 define gf_div(x, y)
 101 {
 102   local l;
 103   l = gfx_div(x, y);
 104   return gf(l[[0]]);
 105 }
 106
 107 define gf_mod(x, y)
 108 {
 109   local l;
 110   l = gfx_div(x, y);
 111   return gf(l[[1]]);
 112 }
 113
 114 define gf_inv(a, b)
 115 {
 116   local g, x, y, X, Y, u, v, t, q, r;
 117   x = gf(1); X = gf(0);
 118   y = gf(0); Y = gf(1);
 119
 120   if (b == gf(0)) { g = a; } else if (a == gf(0)) { g = b; }
 121   else {
 122     while (b != gf(0)) {
 123       q = gf_div(b, a); r = gf_mod(b, a);
 124       t = X * q + x; x = X; X = t;
 125       t = Y * q + y; y = Y; Y = t;
 126       b = a; a = r;
 127     }
 128     g = a;
 129   }
 130   if (g != gf(1)) quit "not coprime in gf_inv";
 131   return Y;
 132 }
 133
 134 /*----- That's all, folks -------------------------------------------------*/