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

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