--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: gfn.c,v 1.1 2004/04/01 21:28:41 mdw Exp $
+ *
+ * Normal-basis translation for binary fields
+ *
+ * (c) 2004 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This file is part of Catacomb.
+ *
+ * Catacomb is free software; you can redistribute it and/or modify
+ * 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: gfn.c,v $
+ * Revision 1.1 2004/04/01 21:28:41 mdw
+ * Normal basis support (translates to poly basis internally). Rewrite
+ * EC and prime group table generators in awk, so that they can reuse data
+ * for repeated constants.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "gfreduce.h"
+#include "gfn.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @gfn_copy@ --- *
+ *
+ * Arguments: @gfn *d@ = where to put the copy
+ * @const gfn *s@ = where the source is
+ *
+ * Returns: ---
+ *
+ * Use: Makes a copy of a translation matrix.
+ */
+
+void gfn_copy(gfn *d, const gfn *s)
+{
+ size_t i;
+
+ d->n = s->n;
+ d->r = xmalloc(s->n * sizeof(mp *));
+ for (i = 0; i < s->n; i++)
+ d->r[i] = MP_COPY(s->r[i]);
+}
+
+/* --- @gfn_destroy@ --- *
+ *
+ * Arguments: @gfn *m@ = a transformation matrix to free
+ *
+ * Returns: ---
+ *
+ * Use: Frees up a transformation matrix when it's no longer wanted.
+ */
+
+void gfn_destroy(gfn *m)
+ { size_t i; for (i = 0; i < m->n; i++) MP_DROP(m->r[i]); xfree(m->r); }
+
+/* --- @gfn_identity@ --- *
+ *
+ * Arguments: @gfn *m@ = where to put the matrix
+ * @size_t n@ = size of the matrix
+ *
+ * Returns: ---
+ *
+ * Use: Fills @m@ with an identity matrix.
+ */
+
+void gfn_identity(gfn *m, size_t n)
+{
+ size_t i;
+
+ m->n = n;
+ m->r = xmalloc(n * sizeof(mp *));
+ m->r[0] = MP_ONE;
+ for (i = 1; i < n; i++)
+ m->r[i] = mp_lsl(MP_NEW, m->r[i - 1], 1);
+}
+
+/* --- @gfn_invert@ --- *
+ *
+ * Arguments: @gfn *m@ = a transformation matrix
+ *
+ * Returns: Zero if successful, nonzero if the matrix was singular.
+ *
+ * Use: Inverts a transformation matrix.
+ */
+
+int gfn_invert(gfn *m)
+{
+ size_t i, j;
+ gfn mm;
+ mp *t;
+ int rc = -1;
+
+ mm = *m;
+ gfn_identity(m, mm.n);
+ for (i = 0; i < mm.n; i++) {
+ if (!mp_testbit(mm.r[i], i)) {
+ for (j = i + 1; j < mm.n; j++) {
+ if (mp_testbit(mm.r[j], i))
+ goto found_set;
+ }
+ goto fail;
+ found_set:
+ t = mm.r[i]; mm.r[i] = mm.r[j]; mm.r[j] = t;
+ t = m->r[i]; m->r[i] = m->r[j]; m->r[j] = t;
+ }
+ for (j = 0; j < mm.n; j++) {
+ if (j == i) continue;
+ if (mp_testbit(mm.r[j], i)) {
+ mm.r[j] = mp_xor(mm.r[j], mm.r[j], mm.r[i]);
+ m->r[j] = mp_xor(m->r[j], m->r[j], m->r[i]);
+ }
+ }
+ }
+ rc = 0;
+fail:
+ gfn_destroy(&mm);
+ return (rc);
+}
+
+/* --- @gfn_transform@ --- *
+ *
+ * Arguments: @gfn *m@ = conversion matrix to apply
+ * @mp *d@ = destination pointer
+ * @mp *x@ = input value
+ *
+ * Returns: The transformed element.
+ *
+ * Use: Transforms a field element according to the given matrix.
+ */
+
+mp *gfn_transform(gfn *m, mp *d, mp *x)
+{
+ mp *y = MP_ZERO;
+ size_t i;
+ mpscan sc;
+
+ for (i = 0, mp_scan(&sc, x); i < m->n && mp_step(&sc); i++)
+ if (mp_bit(&sc)) y = mp_xor(y, y, m->r[i]);
+ mp_drop(d);
+ return (y);
+}
+
+/* --- @gfn_create@ --- *
+ *
+ * Arguments: @mp *p@ = modulus for polynomial basis
+ * @mp *beta@ = the generator of the normal basis, expressed
+ * relative to the polynomial basis
+ * @gfn *ntop@ = output normal-to-polynomail conversion matrix
+ * @gfn *pton@ = output polynomial-to-normal conversion matrix
+ *
+ * Returns: Zero if it worked, nonzero otherwise (e.g., if %$\beta$%
+ * doesn't generate a proper basis).
+ *
+ * Use: Constructs conversion matrices between polynomial and normal
+ * basis representations of binary field elements.
+ */
+
+int gfn_create(mp *p, mp *beta, gfn *ntop, gfn *pton)
+{
+ size_t m = mp_bits(p) - 1;
+ size_t i;
+ gfreduce gr;
+ gfn *np, tmp;
+
+ /* --- We start by building the the @ntop@ matrix --- *
+ *
+ * For mad reasons, the string representation of normal-basis elements is
+ * backwards.
+ */
+
+ gfreduce_create(&gr, p);
+ np = ntop ? ntop : &tmp;
+ np->n = m;
+ np->r = xmalloc(m * sizeof(mp *));
+ np->r[m - 1] = MP_COPY(beta);
+ for (i = m - 1; i--; ) {
+ mp *x = gf_sqr(MP_NEW, np->r[i + 1]);
+ np->r[i] = gfreduce_do(&gr, x, x);
+ }
+ gfreduce_destroy(&gr);
+
+ /* --- That was easy -- now invert it --- */
+
+ if (pton) {
+ if (ntop) gfn_copy(pton, np); else *pton = *np;
+ if (gfn_invert(pton)) {
+ gfn_destroy(pton);
+ if (ntop) gfn_destroy(ntop);
+ return (-1);
+ }
+ }
+
+ /* --- And we're done --- */
+
+ return (0);
+}
+
+/*----- Test rig ----------------------------------------------------------*/
+
+#ifdef TEST_RIG
+
+static int check(dstr *v)
+{
+ mp *p = *(mp **)v[0].buf;
+ mp *beta = *(mp **)v[1].buf;
+ mp *xp = *(mp **)v[2].buf;
+ mp *xn = *(mp **)v[3].buf;
+ mp *y = MP_NEW;
+ gfn pton, ntop, ii;
+ size_t i;
+ int ok = 1;
+
+ gfn_create(p, beta, &ntop, &pton);
+ gfn_identity(&ii, pton.n);
+ for (i = 0; i < pton.n; i++) {
+ y = gfn_transform(&ntop, y, pton.r[i]);
+ if (!MP_EQ(y, ii.r[i])) {
+ ok = 0;
+ fprintf(stderr, "*** inverse pton->ntop check failed (row %lu)\n",
+ (unsigned long)i);
+ MP_EPRINTX("*** p", p); MP_EPRINTX("*** beta", beta);
+ MP_EPRINTX("*** computed", y);
+ }
+ }
+ gfn_destroy(&ii);
+ y = gfn_transform(&pton, y, xp);
+ if (!MP_EQ(y, xn)) {
+ ok = 0;
+ fprintf(stderr, "*** pton failed\n");
+ MP_EPRINTX("*** p", p); MP_EPRINTX("*** beta", beta);
+ MP_EPRINTX("*** xp", xp); MP_EPRINTX("*** xn", xn);
+ MP_EPRINTX("*** computed", y);
+ }
+ y = gfn_transform(&ntop, y, xn);
+ if (!MP_EQ(y, xp)) {
+ ok = 0;
+ fprintf(stderr, "*** ntop failed\n");
+ MP_EPRINTX("*** p", p); MP_EPRINTX("*** beta", beta);
+ MP_EPRINTX("*** xp", xp); MP_EPRINTX("*** xn", xn);
+ MP_EPRINTX("*** computed", y);
+ }
+ gfn_destroy(&pton); gfn_destroy(&ntop);
+ mp_drop(p); mp_drop(beta); mp_drop(xp); mp_drop(xn); mp_drop(y);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
+static test_chunk tests[] = {
+ { "gfn", check, { &type_mp, &type_mp, &type_mp, &type_mp } },
+ { 0 }
+};
+
+int main(int argc, char *argv[])
+{
+ test_run(argc, argv, tests, SRCDIR "/tests/gfn");
+ return (0);
+}
+
+#endif
+
+/*----- That's all, folks -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff