gdsa: Include "dsa.h" for dsa_h2n.

[u/mdw/catacomb] / gf-arith.c

diff --git a/gf-arith.c b/gf-arith.c
index debfba1..5a7b3f2 100644 (file)
--- a/gf-arith.c
+++ b/gf-arith.c
@@ -1,13 +1,13 @@
 /* -*-c-*-
  *
- * $Id: gf-arith.c,v 1.2 2004/03/21 22:52:06 mdw Exp $
+ * $Id$
  *
  * Basic arithmetic on binary polynomials
  *
  * (c) 2004 Straylight/Edgeware
  */
 
-/*----- Licensing notice --------------------------------------------------* 
+/*----- Licensing notice --------------------------------------------------*
  *
  * This file is part of Catacomb.
  *
@@ -15,29 +15,18 @@
  * it under the terms of the GNU Library General Public License as
  * published by the Free Software Foundation; either version 2 of the
  * License, or (at your option) any later version.
- * 
+ *
  * Catacomb is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU Library General Public License for more details.
- * 
+ *
  * You should have received a copy of the GNU Library General Public
  * License along with Catacomb; if not, write to the Free
  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  * MA 02111-1307, USA.
  */
 
-/*----- Revision history --------------------------------------------------* 
- *
- * $Log: gf-arith.c,v $
- * Revision 1.2  2004/03/21 22:52:06  mdw
- * Merge and close elliptic curve branch.
- *
- * Revision 1.1.2.1  2004/03/21 22:39:46  mdw
- * Elliptic curves on binary fields work.
- *
- */
-
 /*----- Header files ------------------------------------------------------*/
 
 #include "gf.h"
@@ -85,8 +74,8 @@ mp *gf_mul(mp *d, mp *a, mp *b)
     size_t m = MAX(MP_LEN(a), MP_LEN(b));
     mpw *s;
     MP_DEST(d, 2 * m, a->f | b->f | MP_UNDEF);
-    s = mpalloc(d->a, 2 * m);
-    gfx_kmul(d->v, d->vl, a->v, a->vl, b->v, b->vl, s, s + 2 * m);
+    s = mpalloc(d->a, 3 * m);
+    gfx_kmul(d->v, d->vl, a->v, a->vl, b->v, b->vl, s, s + 3 * m);
     mpfree(d->a, s);
   }
 
@@ -181,6 +170,39 @@ void gf_div(mp **qq, mp **rr, mp *a, mp *b)
   }
 }
 
+/* --- @gf_irreduciblep@ --- *
+ *
+ * Arguments:  @mp *f@ = a polynomial
+ *
+ * Returns:    Nonzero if the polynomial is irreducible; otherwise zero.
+ */
+
+int gf_irreduciblep(mp *f)
+{
+  unsigned long m;
+  mp *u = MP_TWO;
+  mp *v = MP_NEW;
+
+  if (MP_ZEROP(f))
+    return (0);
+  else if (MP_LEN(f) == 1) {
+    if (f->v[0] < 2) return (0);
+    if (f->v[0] < 4) return (1);
+  }
+  m = (mp_bits(f) - 1)/2;
+  while (m) {
+    u = gf_sqr(u, u);
+    gf_div(0, &u, u, f);
+    v = gf_add(v, u, MP_TWO);
+    gf_gcd(&v, 0, 0, v, f);
+    if (!MP_EQ(v, MP_ONE)) break;
+    m--;
+  }
+  MP_DROP(u);
+  MP_DROP(v);
+  return (!m);
+}
+
 /*----- Test rig ----------------------------------------------------------*/
 
 #ifdef TEST_RIG
@@ -189,8 +211,8 @@ static int verify(const char *op, mp *expect, mp *result, mp *a, mp *b)
 {
   if (!MP_EQ(expect, result)) {
     fprintf(stderr, "\n*** %s failed", op);
-    fputs("\n*** a      = ", stderr); mp_writefile(a, stderr, 16);
-    fputs("\n*** b      = ", stderr); mp_writefile(b, stderr, 16);
+    fputs("\n*** a     = ", stderr); mp_writefile(a, stderr, 16);
+    fputs("\n*** b     = ", stderr); mp_writefile(b, stderr, 16);
     fputs("\n*** result = ", stderr); mp_writefile(result, stderr, 16);
     fputs("\n*** expect = ", stderr); mp_writefile(expect, stderr, 16);
     fputc('\n', stderr);
@@ -214,6 +236,7 @@ static int verify(const char *op, mp *expect, mp *result, mp *a, mp *b)
 
 RIG(add, gf_add)
 RIG(mul, gf_mul)
+RIG(exp, gf_exp)
 
 #undef RIG
 
@@ -246,11 +269,31 @@ static int tdiv(dstr *v)
   return (ok);
 }
 
+static int tirred(dstr *v)
+{
+  mp *a = *(mp **)v[0].buf;
+  int r = *(int *)v[1].buf;
+  int c = gf_irreduciblep(a);
+  int ok = 1;
+  if (r != c) {
+    ok = 0;
+    fprintf(stderr, "\n*** irred failed");
+    fputs("\n*** a     = ", stderr); mp_writefile(a, stderr, 16);
+    fprintf(stderr, "\n*** r     = %d\n", r);
+    fprintf(stderr, "*** c     = %d\n", c);
+  }
+  mp_drop(a);
+  assert(mparena_count(MPARENA_GLOBAL) == 0);
+  return (ok);
+}
+
 static test_chunk tests[] = {
   { "add", tadd, { &type_mp, &type_mp, &type_mp, 0 } },
   { "mul", tmul, { &type_mp, &type_mp, &type_mp, 0 } },
   { "sqr", tsqr, { &type_mp, &type_mp, 0 } },
   { "div", tdiv, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } },
+  { "exp", texp, { &type_mp, &type_mp, &type_mp, 0 } },
+  { "irred", tirred, { &type_mp, &type_int, 0 } },
   { 0, 0, { 0 } },
 };