chiark - git - mdw - catacomb/blob - pgen-safe.c

   1 /* -*-c-*-
   2  *
   3  * $Id: pgen-safe.c,v 1.5 2004/04/08 01:36:15 mdw Exp $
   4  *
   5  * Safe prime generation
   6  *
   7  * (c) 1999 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 /*----- Header files ------------------------------------------------------*/
  31
  32 #include "mp.h"
  33 #include "mprand.h"
  34 #include "pgen.h"
  35
  36 /*----- Main code ---------------------------------------------------------*/
  37
  38 /* --- @pgen_safestep@ --- *
  39  *
  40  * Steps two numbers, %$q$% and %$p = 2q + 1$%, such that neither has any
  41  * small factors.  %$p$% is put in the event block.
  42  */
  43
  44 int pgen_safestep(int rq, pgen_event *ev, void *p)
  45 {
  46   pgen_safestepctx *c = p;
  47   int rc = PGEN_ABORT, qrc = 0;
  48
  49   switch (rq) {
  50
  51     /* --- Set up the contexts --- */
  52
  53     case PGEN_BEGIN: {
  54       mp *p = mp_split(MP_COPY(ev->m));
  55       mp *q;
  56       p->v[0] |= 3;
  57       q = mp_lsr(MP_NEW, p, 1);
  58       rc = pfilt_create(&c->p, p);
  59       qrc = pfilt_create(&c->q, q);
  60       mp_drop(p); mp_drop(q);
  61     } break;
  62
  63     /* --- Step along --- */
  64
  65     case PGEN_TRY:
  66       mp_drop(ev->m);
  67       rc = pfilt_step(&c->p, 4);
  68       qrc = pfilt_step(&c->q, 2);
  69       break;
  70
  71       break;
  72
  73     /* --- Tidy the toys away --- */
  74
  75     case PGEN_DONE:
  76       pfilt_destroy(&c->q);
  77       pfilt_destroy(&c->p);
  78       return (PGEN_DONE);
  79   }
  80
  81   /* --- Continue stepping if necessary --- */
  82
  83   while (rc == PGEN_FAIL || qrc == PGEN_FAIL) {
  84     rc = pfilt_step(&c->p, 4);
  85     qrc = pfilt_step(&c->q, 2);
  86   }
  87
  88   ev->m = MP_COPY(c->p.m);
  89   if (qrc == PGEN_TRY)
  90     rc = PGEN_TRY;
  91   return (rc);
  92 }
  93
  94 /* --- @pgen_safejump@ --- *
  95  *
  96  * Jumps two numbers, %$q$% and %$p = 2q + 1$% such that neither has any
  97  * small factors.
  98  */
  99
 100 int pgen_safejump(int rq, pgen_event *ev, void *p)
 101 {
 102   pgen_safejumpctx *j = p;
 103   int rc = PGEN_ABORT, qrc = 0;
 104
 105   switch (rq) {
 106
 107     /* --- Set up the jump contexts --- *
 108      *
 109      * The jump in @j.q@ is congruent to 2 (mod 4); see @strongprime_setup@.
 110      * If @p@ is initially 1 (mod 4) then add @j.q@.  Then double @j.q@ to
 111      * ensure that the step is 0 (mod 4).  Ensure that @jq@ and @q@ don't
 112      * have any common factors.
 113      */
 114
 115     case PGEN_BEGIN: {
 116       mp *p = ev->m;
 117       mp *q;
 118       mp *g = MP_NEW;
 119       if ((p->v[0] & 3) != 3)
 120         p = mp_add(p, p, j->jq.m);
 121       q = mp_lsr(MP_NEW, p, 1);
 122       mp_gcd(&g, 0, 0, p, j->jq.m);
 123       if (MP_CMP(g, >, MP_ONE)) {
 124         ev->m = p;
 125         mp_drop(q);
 126         mp_drop(g);
 127         return (PGEN_ABORT);
 128       }
 129       mp_drop(g);
 130       rc = pfilt_create(&j->p, p);
 131       pfilt_muladd(&j->jp, &j->jq, 2, 0);
 132       qrc = pfilt_create(&j->q, q);
 133       mp_drop(p);
 134       mp_drop(q);
 135     } break;
 136
 137     /* --- Step on one place --- */
 138
 139     case PGEN_TRY:
 140       mp_drop(ev->m);
 141       rc = pfilt_jump(&j->p, &j->jp);
 142       qrc = pfilt_jump(&j->q, &j->jq);
 143       break;
 144
 145     /* --- Tidy everything up --- */
 146
 147     case PGEN_DONE:
 148       pfilt_destroy(&j->jp);
 149       pfilt_destroy(&j->p);
 150       pfilt_destroy(&j->q);
 151       return (PGEN_DONE);
 152   }
 153
 154   /* --- Step on while @p@ or @q@ have small factors --- */
 155
 156   while (rc == PGEN_FAIL || qrc == PGEN_FAIL) {
 157     rc = pfilt_jump(&j->p, &j->jp);
 158     qrc = pfilt_jump(&j->q, &j->jq);
 159   }
 160   ev->m = MP_COPY(j->p.m);
 161   if (qrc == PGEN_TRY)
 162     rc = PGEN_TRY;
 163   return (rc);
 164 }
 165
 166 /* --- @pgen_safetest@ --- *
 167  *
 168  * Applies Rabin-Miller tests to %$p$% and %$q$%.
 169  */
 170
 171 int pgen_safetest(int rq, pgen_event *ev, void *p)
 172 {
 173   pgen_safetestctx *c = p;
 174   int rc = PGEN_ABORT;
 175
 176   switch (rq) {
 177     case PGEN_BEGIN:
 178       rabin_create(&c->q, c->c.q.m);
 179       rabin_create(&c->p, c->c.p.m);
 180       rc = PGEN_TRY;
 181       break;
 182     case PGEN_TRY: {
 183       mp *m = mprand_range(MP_NEW, c->c.p.m, ev->r, 0);
 184       rc = rabin_test(&c->p, m);
 185       if (rc == PGEN_PASS) {
 186         m = mprand_range(m, c->c.q.m, ev->r, 0);
 187         rc = rabin_test(&c->q, m);
 188       }
 189       mp_drop(m);
 190     } break;
 191     case PGEN_DONE:
 192       rabin_destroy(&c->q);
 193       rabin_destroy(&c->p);
 194       break;
 195   }
 196   return (rc);
 197 }
 198
 199 /*----- That's all, folks -------------------------------------------------*/