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

   1 /* -*-c-*-
   2  *
   3  * $Id: f-niceprime.c,v 1.2 2004/03/27 17:54:11 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.2  2004/03/27 17:54:11  mdw
  34  * Standard curves and curve checking.
  35  *
  36  * Revision 1.1  2004/03/27 00:04:46  mdw
  37  * Implement efficient reduction for pleasant-looking primes.
  38  *
  39  */
  40
  41 /*----- Header files ------------------------------------------------------*/
  42
  43 #include <mLib/sub.h>
  44
  45 #include "field.h"
  46 #include "mpreduce.h"
  47 #include "mprand.h"
  48
  49 /*----- Data structures ---------------------------------------------------*/
  50
  51 typedef struct fctx {
  52   field f;
  53   mpreduce r;
  54 } fctx;
  55
  56 /*----- Main code ---------------------------------------------------------*/
  57
  58 /* --- Field operations --- */
  59
  60 static void fdestroy(field *ff)
  61 {
  62   fctx *f = (fctx *)ff;
  63   mpreduce_destroy(&f->r);
  64   DESTROY(f);
  65 }
  66
  67 static mp *frand(field *ff, mp *d, grand *r)
  68 {
  69   fctx *f = (fctx *)ff;
  70   return (mprand_range(d, f->r.p, r, 0));
  71 }
  72
  73 static int fzerop(field *ff, mp *x)
  74 {
  75   return (!MP_LEN(x));
  76 }
  77
  78 static mp *fneg(field *ff, mp *d, mp *x)
  79 {
  80   fctx *f = (fctx *)ff;
  81   return (mp_sub(d, f->r.p, x));
  82 }
  83
  84 static mp *fadd(field *ff, mp *d, mp *x, mp *y)
  85 {
  86   fctx *f = (fctx *)ff;
  87   d = mp_add(d, x, y);
  88   if (d->f & MP_NEG)
  89     d = mp_add(d, d, f->r.p);
  90   else if (MP_CMP(d, >, f->r.p))
  91     d = mp_sub(d, d, f->r.p);
  92   return (d);
  93 }
  94
  95 static mp *fsub(field *ff, mp *d, mp *x, mp *y)
  96 {
  97   fctx *f = (fctx *)ff;
  98   d = mp_sub(d, x, y);
  99   if (d->f & MP_NEG)
 100     d = mp_add(d, d, f->r.p);
 101   else if (MP_CMP(d, >, f->r.p))
 102     d = mp_sub(d, d, f->r.p);
 103   return (d);
 104 }
 105
 106 static mp *fmul(field *ff, mp *d, mp *x, mp *y)
 107 {
 108   fctx *f = (fctx *)ff;
 109   d = mp_mul(d, x, y);
 110   return (mpreduce_do(&f->r, d, d));
 111 }
 112
 113 static mp *fsqr(field *ff, mp *d, mp *x)
 114 {
 115   fctx *f = (fctx *)ff;
 116   d = mp_sqr(d, x);
 117   return (mpreduce_do(&f->r, d, d));
 118 }
 119
 120 static mp *finv(field *ff, mp *d, mp *x)
 121 {
 122   fctx *f = (fctx *)ff;
 123   mp_gcd(0, 0, &d, f->r.p, x);
 124   return (d);
 125 }
 126
 127 static mp *freduce(field *ff, mp *d, mp *x)
 128 {
 129   fctx *f = (fctx *)ff;
 130   return (mpreduce_do(&f->r, d, x));
 131 }
 132
 133 static mp *fsqrt(field *ff, mp *d, mp *x)
 134 {
 135   fctx *f = (fctx *)ff;
 136   return (mp_modsqrt(d, x, f->r.p));
 137 }
 138
 139 static mp *fdbl(field *ff, mp *d, mp *x)
 140 {
 141   fctx *f = (fctx *)ff;
 142   d = mp_lsl(d, x, 1);
 143   if (MP_CMP(d, >, f->r.p))
 144     d = mp_sub(d, d, f->r.p);
 145   return (d);
 146 }
 147
 148 static mp *ftpl(field *ff, mp *d, mp *x)
 149 {
 150   fctx *f = (fctx *)ff;
 151   MP_DEST(d, MP_LEN(x) + 1, x->f);
 152   MPX_UMULN(d->v, d->vl, x->v, x->vl, 3);
 153   while (MP_CMP(d, >, f->r.p))
 154     d = mp_sub(d, d, f->r.p);
 155   return (d);
 156 }
 157
 158 static mp *fqdl(field *ff, mp *d, mp *x)
 159 {
 160   fctx *f = (fctx *)ff;
 161   d = mp_lsl(d, x, 2);
 162   while (MP_CMP(d, >, f->r.p))
 163     d = mp_sub(d, d, f->r.p);
 164   return (d);
 165 }
 166
 167 static mp *fhlv(field *ff, mp *d, mp *x)
 168 {
 169   fctx *f = (fctx *)ff;
 170   if (!MP_LEN(x)) {
 171     MP_COPY(x);
 172     MP_DROP(d);
 173     return (x);
 174   }
 175   if (x->v[0] & 1) {
 176     d = mp_add(d, x, f->r.p);
 177     x = d;
 178   }
 179   return (mp_lsr(d, x, 1));
 180 }
 181
 182 /* --- Field operations table --- */
 183
 184 static field_ops fops = {
 185   FTY_PRIME, "niceprime",
 186   fdestroy, frand,
 187   freduce, field_id,
 188   fzerop, fneg, fadd, fsub, fmul, fsqr, finv, freduce, fsqrt,
 189   0,
 190   fdbl, ftpl, fqdl, fhlv
 191 };
 192
 193 /* --- @field_niceprime@ --- *
 194  *
 195  * Arguments:   @mp *p@ = the characteristic of the field
 196  *
 197  * Returns:     A pointer to the field.
 198  *
 199  * Use:         Creates a field structure for a prime field of size %$p$%,
 200  *              using efficient reduction for nice primes.
 201  */
 202
 203 field *field_niceprime(mp *p)
 204 {
 205   fctx *f = CREATE(fctx);
 206   f->f.ops = &fops;
 207   f->f.zero = MP_ZERO;
 208   f->f.one = MP_ONE;
 209   f->f.nbits = mp_bits(p);
 210   f->f.noctets = (f->f.nbits + 7) >> 3;
 211   mpreduce_create(&f->r, p);
 212   f->f.m = f->r.p;
 213   return (&f->f);
 214 }
 215
 216 /*----- That's all, folks -------------------------------------------------*/