chiark - git - mdw - catacomb/blob - f-niceprime.c

   1 /* -*-c-*-
   2  *
   3  * $Id: f-niceprime.c,v 1.3 2004/04/01 12:50:09 mdw Exp $
   4  *
   5  * Prime fields with efficient reduction for special-form primes
   6  *
   7  * (c) 2004 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: f-niceprime.c,v $
  33  * Revision 1.3  2004/04/01 12:50:09  mdw
  34  * Add cyclic group abstraction, with test code.  Separate off exponentation
  35  * functions for better static linking.  Fix a buttload of bugs on the way.
  36  * Generally ensure that negative exponents do inversion correctly.  Add
  37  * table of standard prime-field subgroups.  (Binary field subgroups are
  38  * currently unimplemented but easy to add if anyone ever finds a good one.)
  39  *
  40  * Revision 1.2  2004/03/27 17:54:11  mdw
  41  * Standard curves and curve checking.
  42  *
  43  * Revision 1.1  2004/03/27 00:04:46  mdw
  44  * Implement efficient reduction for pleasant-looking primes.
  45  *
  46  */
  47
  48 /*----- Header files ------------------------------------------------------*/
  49
  50 #include <mLib/sub.h>
  51
  52 #include "field.h"
  53 #include "mpreduce.h"
  54 #include "mprand.h"
  55
  56 /*----- Data structures ---------------------------------------------------*/
  57
  58 typedef struct fctx {
  59   field f;
  60   mpreduce r;
  61 } fctx;
  62
  63 /*----- Main code ---------------------------------------------------------*/
  64
  65 /* --- Field operations --- */
  66
  67 static void fdestroy(field *ff)
  68 {
  69   fctx *f = (fctx *)ff;
  70   mpreduce_destroy(&f->r);
  71   DESTROY(f);
  72 }
  73
  74 static mp *frand(field *ff, mp *d, grand *r)
  75 {
  76   fctx *f = (fctx *)ff;
  77   return (mprand_range(d, f->r.p, r, 0));
  78 }
  79
  80 static int fzerop(field *ff, mp *x)
  81 {
  82   return (!MP_LEN(x));
  83 }
  84
  85 static mp *fneg(field *ff, mp *d, mp *x)
  86 {
  87   fctx *f = (fctx *)ff;
  88   return (mp_sub(d, f->r.p, x));
  89 }
  90
  91 static mp *fadd(field *ff, mp *d, mp *x, mp *y)
  92 {
  93   fctx *f = (fctx *)ff;
  94   d = mp_add(d, x, y);
  95   if (d->f & MP_NEG)
  96     d = mp_add(d, d, f->r.p);
  97   else if (MP_CMP(d, >, f->r.p))
  98     d = mp_sub(d, d, f->r.p);
  99   return (d);
 100 }
 101
 102 static mp *fsub(field *ff, mp *d, mp *x, mp *y)
 103 {
 104   fctx *f = (fctx *)ff;
 105   d = mp_sub(d, x, y);
 106   if (d->f & MP_NEG)
 107     d = mp_add(d, d, f->r.p);
 108   else if (MP_CMP(d, >, f->r.p))
 109     d = mp_sub(d, d, f->r.p);
 110   return (d);
 111 }
 112
 113 static mp *fmul(field *ff, mp *d, mp *x, mp *y)
 114 {
 115   fctx *f = (fctx *)ff;
 116   d = mp_mul(d, x, y);
 117   return (mpreduce_do(&f->r, d, d));
 118 }
 119
 120 static mp *fsqr(field *ff, mp *d, mp *x)
 121 {
 122   fctx *f = (fctx *)ff;
 123   d = mp_sqr(d, x);
 124   return (mpreduce_do(&f->r, d, d));
 125 }
 126
 127 static mp *finv(field *ff, mp *d, mp *x)
 128 {
 129   fctx *f = (fctx *)ff;
 130   mp_gcd(0, 0, &d, f->r.p, x);
 131   return (d);
 132 }
 133
 134 static mp *freduce(field *ff, mp *d, mp *x)
 135 {
 136   fctx *f = (fctx *)ff;
 137   return (mpreduce_do(&f->r, d, x));
 138 }
 139
 140 static mp *fsqrt(field *ff, mp *d, mp *x)
 141 {
 142   fctx *f = (fctx *)ff;
 143   return (mp_modsqrt(d, x, f->r.p));
 144 }
 145
 146 static mp *fdbl(field *ff, mp *d, mp *x)
 147 {
 148   fctx *f = (fctx *)ff;
 149   d = mp_lsl(d, x, 1);
 150   if (MP_CMP(d, >, f->r.p))
 151     d = mp_sub(d, d, f->r.p);
 152   return (d);
 153 }
 154
 155 static mp *ftpl(field *ff, mp *d, mp *x)
 156 {
 157   fctx *f = (fctx *)ff;
 158   MP_DEST(d, MP_LEN(x) + 1, x->f);
 159   MPX_UMULN(d->v, d->vl, x->v, x->vl, 3);
 160   while (MP_CMP(d, >, f->r.p))
 161     d = mp_sub(d, d, f->r.p);
 162   return (d);
 163 }
 164
 165 static mp *fqdl(field *ff, mp *d, mp *x)
 166 {
 167   fctx *f = (fctx *)ff;
 168   d = mp_lsl(d, x, 2);
 169   while (MP_CMP(d, >, f->r.p))
 170     d = mp_sub(d, d, f->r.p);
 171   return (d);
 172 }
 173
 174 static mp *fhlv(field *ff, mp *d, mp *x)
 175 {
 176   fctx *f = (fctx *)ff;
 177   if (!MP_LEN(x)) {
 178     MP_COPY(x);
 179     MP_DROP(d);
 180     return (x);
 181   }
 182   if (x->v[0] & 1) {
 183     d = mp_add(d, x, f->r.p);
 184     x = d;
 185   }
 186   return (mp_lsr(d, x, 1));
 187 }
 188
 189 /* --- Field operations table --- */
 190
 191 static field_ops fops = {
 192   FTY_PRIME, "niceprime",
 193   fdestroy, frand, field_stdsamep,
 194   freduce, field_id,
 195   fzerop, fneg, fadd, fsub, fmul, fsqr, finv, freduce, fsqrt,
 196   0,
 197   fdbl, ftpl, fqdl, fhlv
 198 };
 199
 200 /* --- @field_niceprime@ --- *
 201  *
 202  * Arguments:   @mp *p@ = the characteristic of the field
 203  *
 204  * Returns:     A pointer to the field.
 205  *
 206  * Use:         Creates a field structure for a prime field of size %$p$%,
 207  *              using efficient reduction for nice primes.
 208  */
 209
 210 field *field_niceprime(mp *p)
 211 {
 212   fctx *f = CREATE(fctx);
 213   f->f.ops = &fops;
 214   f->f.zero = MP_ZERO;
 215   f->f.one = MP_ONE;
 216   f->f.nbits = mp_bits(p);
 217   f->f.noctets = (f->f.nbits + 7) >> 3;
 218   mpreduce_create(&f->r, p);
 219   f->f.m = f->r.p;
 220   return (&f->f);
 221 }
 222
 223 /*----- That's all, folks -------------------------------------------------*/