/* -*-c-*-
*
- * $Id: gf-arith.c,v 1.1.2.1 2004/03/21 22:39:46 mdw Exp $
+ * $Id$
*
* Basic arithmetic on binary polynomials
*
* MA 02111-1307, USA.
*/
-/*----- Revision history --------------------------------------------------*
- *
- * $Log: gf-arith.c,v $
- * Revision 1.1.2.1 2004/03/21 22:39:46 mdw
- * Elliptic curves on binary fields work.
- *
- */
-
/*----- Header files ------------------------------------------------------*/
#include "gf.h"
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);
}
}
}
+/* --- @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_bits(f) - 1;
+ mp *u = MP_TWO;
+ mp *v = MP_NEW;
+
+ m /= 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
RIG(add, gf_add)
RIG(mul, gf_mul)
+RIG(exp, gf_exp)
#undef RIG
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 } },
};