Fix up ectab.in a little more. Fix group test vectors broken by new

composite-degree check.  Abortive attempt at determining conversions
for non-optimal Gaussian normal bases -- may as well check in anyway.

diff --git a/ectab.in b/ectab.in
index de594e1..7520b03 100644 (file)
--- a/ectab.in
+++ b/ectab.in
@@ -286,6 +286,9 @@ curve sect571r1 binpoly
   gy 0x037bf27342da639b6dccfffeb73d69d78c6c27a6009cbbca1980f8533921e8a684423e43bab08a576291af8f461bb2a8b3531d2f0485c19b16e2f1516e23dd3c1a4827af1b8ac15b
 
 #----- Curves from ANSI X9.62 -----------------------------------------------
+#
+# The conversion factors for the normal basis representations were generated
+# because none were given in the document.
 
 curve ansi-c2pnb163v1 binpoly
   p 0x080000000000000000000000000000000000000107
@@ -457,7 +460,9 @@ alias ansip521r1 secp521r1
 
 #----- NIST curves from FIPS186-2 -------------------------------------------
 #
-# Most of these are duplicates of SEC2 curves.
+# These are duplicates of SEC2 curves.  However, the normal basis
+# representations aren't in SEC, so we give them here.  (Conversion factors
+# from FIPS186-2.
 
 alias nist-p192 secp192r1
 alias nist-p224 secp224r1
@@ -486,7 +491,6 @@ curve nist-k163n binnorm
   h 2
   gx 0x05679b353caa46825fea2d3713ba450da0c2a4541
   gy 0x235b7c6710050689906bac3d9dec76a835591edb2
-
 curve nist-b163n binnorm
   p 0x800000000000000000000000000000000000000c9
   beta 0x715169c109c612e390d347c748342bcd3b02a0bef
@@ -506,7 +510,6 @@ curve nist-k233n binnorm
   h 4
   gx 0x0fde76d9dcd26e643ac26f1aa901aa129784b71fc0722b2d05614d650b3
   gy 0x0643e317633155c9e0447ba8020a3c43177450ee036d633501434cac978
-
 curve nist-b233n binnorm
   p 0x20000000000000000000000000000000000000004000000000000000001
   beta 0x1499e398ac5d79e368559b35ca49bb7305da6c0390bcf9e2300253203c9
@@ -526,7 +529,6 @@ curve nist-k283n binnorm
   h 4
   gx 0x3ab9593f8db09fc188f1d7c4ac9fcc3e57fcd3bdb15024b212c70229de5fcd92eb0ea60
   gy 0x2118c4755e7345cd8f603ef93b98b106fe8854ffeb9a3b304634cc83a0e759f0c2686b1
-
 curve nist-b283n binnorm
   p 0x800000000000000000000000000000000000000000000000000000000000000000010a1 
   beta 0x31e0ed791c3282dc5624a720818049d053e8c7ab8663792bc1d792eba9867fc7b317a99
@@ -546,7 +548,6 @@ curve nist-k409n binnorm
   h 4
   gx 0x1b559c7cba2422e3affe13343e808b55e012d726ca0b7e6a63aeafbc1e3a98e10ca0fcf98350c3b7f89a9754a8e1dc0713cec4a
   gy 0x16d8c42052f07e7713e7490eff318ba1abd6fef8a5433c894b24f5c817aeb79852496fbee803a47bc8a203878ebf1c499afd7d6
-
 curve nist-b409n binnorm
   p 0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001
   beta 0x0dfa06be206aa97b7a41fffb9b0c55f8f048062fbe8381b4248adf92912ccc8e3f91a24e1cfb3950532b988971c23042e85708d
@@ -566,13 +567,11 @@ curve nist-k571n binnorm
   h 4
   gx 0x04bb2dba418d0db107adae003427e5d7cc139acb465e5934f0bea2ab2f3622bc29b3d5b9aa7a1fdfd5d8be66057c1008e71e484bcd98f22bf8476423767367429ef2ec5bc3ebcf7
   gy 0x44cbb57de20788d2c952d7b56cf39bd3e89b18984bd124e751ceff4369dd8dac6a59e6e745df44d8220ce22aa2c852cfcbbef49ebaa98bd2483e33180e04286feaa253050caff60
-
 curve nist-b571n binnorm
   p 0x80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000425
   beta 0x452186bbf5840a0bcf8c9f02a54efa04e813b43c3d4149606c4d27b487bf107393c8907f79d9778beb35ee87467d3288274caebda6ce05aeb4ca5cf3c3044bd4372232f2c1a27c4
   a 0x7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
   b 0x3762d0d47116006179da35688eeaccf591a5cdea75000118d9608c59132d43426101a1dfb3774115f586623f75f00001ce611983c1275fa31f5bc9f4be1a0f467f01ca885c74777
-
   r 0x03ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe661ce18ff55987308059b186823851ec7dd9ca1161de93d5174d66e8382e9bb2fe84e47
   h 2
   gx 0x0735e035def5925cc33173eb2a8ce7767522b466d278b650a2916127dfea9d2d361089f0a7a0247a184e1c70d417866e0fe0feb0ff8f2f3f9176418f97d117e624e2015df1662a8

diff --git a/tests/group b/tests/group
index 0c2035a..e7ff8e8 100644 (file)
--- a/tests/group
+++ b/tests/group
@@ -1,4 +1,4 @@
-# $Id: group,v 1.2 2004/04/04 19:04:11 mdw Exp $
+# $Id$
 #
 # Test group abstraction, and a bunch of other things.
 
@@ -38,7 +38,7 @@ check {
     0xaa089ae4666a422e714651ad9372213fa65a93,
       0x12d29c630dda76010397809a6816be6d2ffa815
     0xaaaaaaaaaaaaaaaaaab1fcf1e206f421a3ea1b * 12
-  }" "cofactor out of range";
+  }" "degree not prime";
 
 }
 
@@ -253,10 +253,10 @@ fromec {
 }
 
 tobuf {
-  "prime { 29, 7, 16}" 22 -1 "00";
-  "prime { 29, 7, 16}" 22 0 "000116";
-  "prime { 29, 7, 16}" 0 -1 "0000";
-  "prime { 29, 7, 16}" 0 0 "000100";
+  "prime { 29, 7, 16 }" 22 -1 "00";
+  "prime { 29, 7, 16 }" 22 0 "000116";
+  "prime { 29, 7, 16 }" 0 -1 "0000";
+  "prime { 29, 7, 16 }" 0 0 "000100";
 
   "ec { secp112r1 }" inf 0 "0000";
   "ec { secp112r1 }"
@@ -268,10 +268,10 @@ tobuf {
 }
 
 frombuf {
-  "prime { 29, 7, 16}" "00" -1 0;
-  "prime { 29, 7, 16}" "000116" 3 22;
-  "prime { 29, 7, 16}" "00000e" 2 0;
-  "prime { 29, 7, 16}" "000100ff" 3 0;
+  "prime { 29, 7, 16 }" "00" -1 0;
+  "prime { 29, 7, 16 }" "000116" 3 22;
+  "prime { 29, 7, 16 }" "00000e" 2 0;
+  "prime { 29, 7, 16 }" "000100ff" 3 0;
 
   "ec { secp112r1 }" "0000" 2 inf;
   "ec { secp112r1 }"
@@ -284,10 +284,10 @@ frombuf {
 }
 
 toraw {
-  "prime { 29, 7, 16}" 22 -1 "";
-  "prime { 29, 7, 16}" 22 0 "16";
-  "prime { 29, 7, 16}" 0 -1 "";
-  "prime { 29, 7, 16}" 0 0 "00";
+  "prime { 29, 7, 16 }" 22 -1 "";
+  "prime { 29, 7, 16 }" 22 0 "16";
+  "prime { 29, 7, 16 }" 0 -1 "";
+  "prime { 29, 7, 16 }" 0 0 "00";
   "prime { 4294967311, 364289, 18767 }" 4285559121 0 "00ff707151";
   "prime { 4294967311, 364289, 18767 }" 4285559121 -1 "ff707151";
 
@@ -301,9 +301,9 @@ toraw {
 }
 
 fromraw {
-  "prime { 29, 7, 16}" "" -1 0;
-  "prime { 29, 7, 16}" "160bad" 1 22;
-  "prime { 29, 7, 16}" "00" 1 0;
+  "prime { 29, 7, 16 }" "" -1 0;
+  "prime { 29, 7, 16 }" "160bad" 1 22;
+  "prime { 29, 7, 16 }" "00" 1 0;
   "prime { 4294967311, 364289, 18767 }" "00ff707151e7c0" 5 4285559121;
   "prime { 4294967311, 364289, 18767 }" "ff707151" -1 0;
 

diff --git a/utils/fnb.c b/utils/fnb.c
index 8b7c1ab..98941c9 100644 (file)
--- a/utils/fnb.c
+++ b/utils/fnb.c
@@ -1,3 +1,4 @@
+#include <math.h>
 #include <stdio.h>
 #include <stdlib.h>
 
@@ -349,19 +350,28 @@ static unsigned gcd(unsigned u, unsigned v)
   }
 }
 
+static unsigned order(unsigned x, unsigned p)
+{
+  unsigned y, k;
+
+  if (!x || x == 1) return (0);
+  for (y = x, k = 1; y != 1; y = (y*x)%p, k++);
+  return (k);
+}
+
 static int onbtype(unsigned m)
 {
   unsigned t;
   unsigned p, h;
-  unsigned k, x, d;
+  unsigned k, d;
 
   if (m%8 == 0)
     return (0);
-  for (t = 1; t <= 2; t++) {
+  for (t = 1;; t++) {
     p = t*m + 1;
     if (!primep(p))
       continue;
-    for (x = 2, k = 1; x != 1; x = (2*x)%p, k++);
+    k = order(2, p);
     h = t*m/k;
     d = gcd(h, m);
     if (d == 1)
@@ -370,7 +380,9 @@ static int onbtype(unsigned m)
   return (0);
 }
 
-static mp *fieldpoly(unsigned m, int t)
+#define PI 3.1415926535897932384626433832795028841971693993751
+
+static mp *fieldpoly(unsigned m, int t, grand *rr)
 {
   mp *p, *q, *r, *z;
   unsigned i;
@@ -393,8 +405,48 @@ static mp *fieldpoly(unsigned m, int t)
       mp_drop(q);
       mp_drop(r);
       break;
-    default:
-      abort();
+    default: {
+#ifdef notdef
+      unsigned pp = t*m + 1;
+      unsigned uu;
+      unsigned j;
+      struct cplx { double r, i; };
+      struct cplx e, n;
+      struct cplx *f;
+
+      do uu = GR_RANGE(rr, pp); while (order(uu, pp) != t);
+      f = xmalloc(sizeof(struct cplx) * (m + 1));
+      for (i = 0; i <= m; i++) f[i].r = f[i].i = 0;
+      f[0].r = 1;
+      printf("poly init; type = %u\n", t);
+      for (i = m + 1; i--; )
+       printf("%3u: %g + %g i\n", i, f[i].r, f[i].i);
+      putchar('\n');
+      for (i = 1; i <= m; i++) {
+       e.r = e.i = 0;
+       for (j = 0; j < t; j++) {
+         double z = (pow(2, i) * pow(uu, j) * PI)/pp;
+         e.r -= cos(z); e.i -= sin(z);
+       }
+       printf("new factor: %g + %g i\n", e.r, e.i);
+       for (j = i; j--; ) {
+         f[j + 1].r += f[j].r;
+         f[j + 1].i += f[j].i;
+         n.r = f[j].r * e.r - f[j].i * e.i;
+         n.i = f[j].r * e.i + f[j].i * e.r;
+         f[j] = n;
+       }
+       printf("poly after %u iters\n", i);
+       for (j = m + 1; j--; )
+         printf("%3u: %g + %g i\n", j, f[j].r, f[j].i);
+       putchar('\n');
+      }
+      xfree(f);
+      p = MP_ZERO;
+#else
+    abort();
+#endif
+    } break;      
   }
   return (p);
 }
@@ -432,10 +484,10 @@ static mp *fnb(mp *p)
   mp *q, *x;
   unsigned m = mp_bits(p) - 1;
 
-  if ((t = onbtype(m)) == 0)
+  if ((t = onbtype(m)) == 0 || t > 2)
     return (0);
   f = field_binpoly(p);
-  q = fieldpoly(m, t);
+  q = fieldpoly(m, t, r);
   x = poly_solve(f, MP_NEW, q, r);
   MP_DROP(q);
   F_DESTROY(f);