X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/34e4f738bcba58e6d8c4cabbb0b3232a65b42a9d..0f9bd85aa42c06b55d7a4e1693981233d95c62ff:/f-binpoly.c diff --git a/f-binpoly.c b/f-binpoly.c index aeec0cf..5f6a527 100644 --- a/f-binpoly.c +++ b/f-binpoly.c @@ -1,13 +1,13 @@ /* -*-c-*- * - * $Id: f-binpoly.c,v 1.6 2004/04/01 12:50:09 mdw Exp $ + * $Id$ * * Binary fields with polynomial basis representation * * (c) 2004 Straylight/Edgeware */ -/*----- Licensing notice --------------------------------------------------* +/*----- Licensing notice --------------------------------------------------* * * This file is part of Catacomb. * @@ -15,129 +15,78 @@ * 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: f-binpoly.c,v $ - * Revision 1.6 2004/04/01 12:50:09 mdw - * Add cyclic group abstraction, with test code. Separate off exponentation - * functions for better static linking. Fix a buttload of bugs on the way. - * Generally ensure that negative exponents do inversion correctly. Add - * table of standard prime-field subgroups. (Binary field subgroups are - * currently unimplemented but easy to add if anyone ever finds a good one.) - * - * Revision 1.5 2004/03/27 17:54:11 mdw - * Standard curves and curve checking. - * - * Revision 1.4 2004/03/23 15:19:32 mdw - * Test elliptic curves more thoroughly. - * - * Revision 1.3 2004/03/23 12:08:26 mdw - * Random field-element selection. - * - * 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 #include "field.h" -#include "gf.h" -#include "gfreduce.h" +#include "field-guts.h" #include "mprand.h" -/*----- Data structures ---------------------------------------------------*/ - -typedef struct fctx { - field f; - gfreduce r; -} fctx; - -/*----- Main code ---------------------------------------------------------*/ +/*----- Polynomial basis --------------------------------------------------*/ /* --- Field operations --- */ -static void fdestroy(field *ff) -{ - fctx *f = (fctx *)ff; - gfreduce_destroy(&f->r); +static void fdestroy(field *ff) { + fctx_binpoly *f = (fctx_binpoly *)ff; + gfreduce_destroy(&f->r); MP_DROP(f->f.q); DESTROY(f); } -static mp *frand(field *f, mp *d, grand *r) -{ +static mp *frand(field *f, mp *d, grand *r) { return (mprand(d, f->nbits, r, 0)); } -static int fzerop(field *ff, mp *x) -{ - return (!MP_LEN(x)); -} +static int fzerop(field *ff, mp *x) { return (MP_ZEROP(x)); } -static mp *fadd(field *ff, mp *d, mp *x, mp *y) -{ - return (gf_add(d, x, y)); -} +static mp *fadd(field *ff, mp *d, mp *x, mp *y) { return (gf_add(d, x, y)); } -static mp *fmul(field *ff, mp *d, mp *x, mp *y) -{ - fctx *f = (fctx *)ff; - d = gf_mul(d, x, y); +static mp *fmul(field *ff, mp *d, mp *x, mp *y) { + fctx_binpoly *f = (fctx_binpoly *)ff; d = gf_mul(d, x, y); return (gfreduce_do(&f->r, d, d)); } -static mp *fsqr(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - d = gf_sqr(d, x); +static mp *fsqr(field *ff, mp *d, mp *x) { + fctx_binpoly *f = (fctx_binpoly *)ff; d = gf_sqr(d, x); return (gfreduce_do(&f->r, d, d)); } -static mp *finv(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - gf_gcd(0, 0, &d, f->r.p, x); +static mp *finv(field *ff, mp *d, mp *x) { + fctx_binpoly *f = (fctx_binpoly *)ff; + d = gf_modinv(d, x, f->r.p); return (d); } -static mp *freduce(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; +static mp *freduce(field *ff, mp *d, mp *x) { + fctx_binpoly *f = (fctx_binpoly *)ff; return (gfreduce_do(&f->r, d, x)); } -static mp *fsqrt(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; +static mp *fsqrt(field *ff, mp *d, mp *x) { + fctx_binpoly *f = (fctx_binpoly *)ff; return (gfreduce_sqrt(&f->r, d, x)); } -static mp *fquadsolve(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; +static mp *fquadsolve(field *ff, mp *d, mp *x) { + fctx_binpoly *f = (fctx_binpoly *)ff; return (gfreduce_quadsolve(&f->r, d, x)); } /* --- Field operations table --- */ -static field_ops fops = { +static const field_ops fops = { FTY_BINARY, "binpoly", fdestroy, frand, field_stdsamep, freduce, field_id, @@ -157,7 +106,7 @@ static field_ops fops = { field *field_binpoly(mp *p) { - fctx *f = CREATE(fctx); + fctx_binpoly *f = CREATE(fctx_binpoly); f->f.ops = &fops; f->f.zero = MP_ZERO; f->f.one = MP_ONE; @@ -165,7 +114,71 @@ field *field_binpoly(mp *p) f->f.noctets = (f->f.nbits + 7) >> 3; gfreduce_create(&f->r, p); f->f.m = f->r.p; + f->f.q = mp_lsl(MP_NEW, MP_ONE, f->f.nbits); return (&f->f); } +/*----- Normal basis ------------------------------------------------------*/ + +/* --- Field operations --- */ + +static void fndestroy(field *ff) { + fctx_binnorm *f = (fctx_binnorm *)ff; gfreduce_destroy(&f->f.r); + gfn_destroy(&f->ntop); gfn_destroy(&f->pton); MP_DROP(f->f.f.q); + DESTROY(f); +} + +static int fnsamep(field *ff, field *gg) { + fctx_binnorm *f = (fctx_binnorm *)ff, *g = (fctx_binnorm *)gg; + return (MP_EQ(f->ntop.r[0], g->ntop.r[0]) && field_stdsamep(ff, gg)); +} + +static mp *fnin(field *ff, mp *d, mp *x) { + fctx_binnorm *f = (fctx_binnorm *)ff; + return (gfn_transform(&f->ntop, d, x)); +} + +static mp *fnout(field *ff, mp *d, mp *x) { + fctx_binnorm *f = (fctx_binnorm *)ff; + return (gfn_transform(&f->pton, d, x)); +} + +/* --- Field operations table --- */ + +static const field_ops fnops = { + FTY_BINARY, "binnorm", + fndestroy, frand, fnsamep, + fnin, fnout, + fzerop, field_id, fadd, fadd, fmul, fsqr, finv, freduce, fsqrt, + fquadsolve, + 0, 0, 0, 0 +}; + +/* --- @field_binnorm@ --- * + * + * Arguments: @mp *p@ = the reduction polynomial + * @mp *beta@ = representation of normal point + * + * Returns: A pointer to the field. + * + * Use: Creates a field structure for a binary field mod @p@ which + * uses a normal basis representation externally. Computations + * are still done on a polynomial-basis representation. + */ + +field *field_binnorm(mp *p, mp *beta) +{ + fctx_binnorm *f = CREATE(fctx_binnorm); + f->f.f.ops = &fnops; + f->f.f.zero = MP_ZERO; + f->f.f.one = MP_ONE; + f->f.f.nbits = mp_bits(p) - 1; + f->f.f.noctets = (f->f.f.nbits + 7) >> 3; + gfreduce_create(&f->f.r, p); + f->f.f.m = f->f.r.p; + f->f.f.q = mp_lsl(MP_NEW, MP_ONE, f->f.f.nbits); + gfn_create(p, beta, &f->ntop, &f->pton); + return (&f->f.f); +} + /*----- That's all, folks -------------------------------------------------*/