chiark - git - mdw - catacomb/blob - pgen.h

   1 /* -*-c-*-
   2  *
   3  * $Id: pgen.h,v 1.4 1999/12/22 16:01:11 mdw Exp $
   4  *
   5  * Prime generation glue
   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 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: pgen.h,v $
  33  * Revision 1.4  1999/12/22 16:01:11  mdw
  34  * Same file, completely different code.  Main interface for new prime-
  35  * search system.
  36  *
  37  */
  38
  39 #ifndef CATACOMB_PGEN_H
  40 #define CATACOMB_PGEN_H
  41
  42 #ifdef __cplusplus
  43   extern "C" {
  44 #endif
  45
  46 /*----- Header files ------------------------------------------------------*/
  47
  48 #ifndef CATACOMB_GRAND_H
  49 #  include "grand.h"
  50 #endif
  51
  52 #ifndef CATACOMB_MP_H
  53 #  include "mp.h"
  54 #endif
  55
  56 #ifndef CATACOMB_PFILT_H
  57 #  include "pfilt.h"
  58 #endif
  59
  60 #ifndef CATACOMB_RABIN_H
  61 #  include "rabin.h"
  62 #endif
  63
  64 /*----- Event handling ----------------------------------------------------*
  65  *
  66  * Different programs and architectures will want to show progress of prime
  67  * searches and similar processes in different ways.  Of course, for simple
  68  * searches, it's possible to use the @pfilt@ and @rabin@ functions and
  69  * maintain control over the general control flow throughout the search.
  70  *
  71  * For more complex cases, this sort of control is undesirable.  It's
  72  * possible to specify an event handler which is informed in abstract about
  73  * the search.  The event handler can also request the search be aborted.
  74  */
  75
  76 /* --- Event code constants --- *
  77  *
  78  * You're allowed to rely on the values of @PGEN_DONE@ and @PGEN_ABORT@.
  79  */
  80
  81 enum {
  82   PGEN_BEGIN = 1,                       /* Search for value begins */
  83   PGEN_TRY,                             /* A new candidate has appeared */
  84   PGEN_FAIL,                            /* The candidate failed the test */
  85   PGEN_PASS,                            /* The candidate passed a test */
  86   PGEN_DONE = 0,                        /* A good value has been found */
  87   PGEN_ABORT = -1                       /* The search has been aborted */
  88 };
  89
  90 /* --- Event information --- *
  91  *
  92  * Note that the pseudorandom number generator supplied is not
  93  * cryptographically strong.
  94  */
  95
  96 typedef struct pgen_event {
  97   const char *name;                     /* Which quantity is being found */
  98   mp *m;                                /* Current value under test */
  99   unsigned steps;                       /* Number of candidates left */
 100   unsigned tests;                       /* Tests left before passing */
 101   grand *r;                             /* Source of random numbers */
 102 } pgen_event;
 103
 104 /*----- Prime search parameters -------------------------------------------*
 105  *
 106  * The prime search is parameterized in a large number of ways, although this
 107  * isn't so much of a surprise given the different sorts of properties
 108  * required from prime numbers in cryptographic applications.
 109  *
 110  * There are two main things which need to be configured: stepping, and
 111  * testing.  (Filtering is done as part of stepping.)
 112  *
 113  * The functions here provide a toolkit for constructing stepping and testing
 114  * routines.  In a lot of cases, the functions can be used directly; in
 115  * others, simple bits of glue need be written.
 116  *
 117  * Two types of functions are defined: steppers and testers, but their
 118  * interfaces are substantially similar.  Each is given a request code, a
 119  * context block and an event block.  It is meant to update its context and
 120  * the event block and return an event code.
 121  *
 122  * A call with a request of @PGEN_BEGIN@ asks the stepper or tester to
 123  * initialize itself using the information in its event block and context.  A
 124  * return of @PGEN_FAIL@ reports an immediate failure; @PGEN_ABORT@ reports a
 125  * fatal problem; @PGEN_DONE@ reports immediate success.  @PGEN_TRY@ reports
 126  * successful initialization and requests test iterations.
 127  *
 128  * A call to a stepper with a request of @PGEN_TRY@ asks it to step to the
 129  * next possible candidate, replacing the value @m@ in the event block with
 130  * the new candidate.  A call to a tester with a request of @PGEN_TRY@
 131  * runs one pass of the test.  It should return @PGEN_FAIL@ to report a
 132  * failure, @PGEN_PASS@ to report a success and request another iteration,
 133  * @PGEN_DONE@ to report final acceptance and @PGEN_ABORT@ to terminate the
 134  * search unsuccessfully.  Note that even if the search is aborted, a
 135  * shutdown request is still made.
 136  *
 137  * A call with a request of @PGEN_DONE@ closes down the stepper or tester.
 138  * After a successful initialization (i.e., a return of something other than
 139  * @PGEN_ABORT@), a shutdown call is guaranteed.  The return code is ignored.
 140  */
 141
 142 typedef int pgen_proc(int /*rq*/, pgen_event */*ev*/, void */*p*/);
 143
 144 /*----- Simple handler functions ------------------------------------------*/
 145
 146 /* --- @pgen_filter@ --- *
 147  *
 148  * A prime generation context contains the information required for the
 149  * simple prime filter and tester presented here.
 150  */
 151
 152 typedef struct pgen_filterctx {
 153   unsigned step;                        /* Step size (set by client) */
 154   pfilt f;                              /* The rapid prime filter */
 155 } pgen_filterctx;
 156
 157 extern int pgen_filter(int /*rq*/, pgen_event */*ev*/, void */*p*/);
 158
 159 /* --- @pgen_jump@ --- *
 160  *
 161  * Similar to the standard @pgen_filter@, but jumps in large steps rather
 162  * than small ones.
 163  */
 164
 165 typedef struct pgen_jumpctx {
 166   const pfilt *j;
 167   pfilt f;
 168 } pgen_jumpctx;
 169
 170 extern int pgen_jump(int /*rq*/, pgen_event */*ev*/, void */*p*/);
 171
 172 /* --- @pgen_test@ --- *
 173  *
 174  * Runs the Rabin-Miller primality test.  The context block is simply a
 175  * @rabin@ context.
 176  */
 177
 178 extern int pgen_test(int /*rq*/, pgen_event */*ev*/, void */*p*/);
 179
 180 /*----- Safe prime functions ----------------------------------------------*/
 181
 182 /* --- @pgen_safestep@ --- *
 183  *
 184  * Steps two numbers, %$q$% and %$p = 2q + 1$%, such that neither has any
 185  * small factors.  %$p$% is put in the event block.
 186  */
 187
 188 typedef struct pgen_safestepctx {
 189   pfilt q, p;
 190 } pgen_safestepctx;
 191
 192 extern int pgen_safestep(int /*rq*/, pgen_event */*ev*/, void */*p*/);
 193
 194 /* --- @pgen_safetest@ --- *
 195  *
 196  * Applies Rabin-Miller tests to %$p$% and %$(p - 1)/2$%.
 197  */
 198
 199 typedef struct pgen_safetestctx {
 200   pgen_safestepctx c;
 201   rabin q, p;
 202 } pgen_safetestctx;
 203
 204 extern int pgen_safetest(int /*rq*/, pgen_event */*ev*/, void */*p*/);
 205
 206 /*----- Standard event handlers -------------------------------------------*/
 207
 208 /* --- @pgen_evspin@ --- *
 209  *
 210  * Displays a spinning baton to show progress.
 211  */
 212
 213 extern int pgen_evspin(int /*rq*/, pgen_event */*ev*/, void */*p*/);
 214
 215 /* --- @pgen_ev@ --- *
 216  *
 217  * Traditional event handler, shows dots for each test.
 218  */
 219
 220 extern int pgen_ev(int /*rq*/, pgen_event */*ev*/, void */*p*/);
 221
 222 /*----- The main driver ---------------------------------------------------*/
 223
 224 /* --- @pgen@ --- *
 225  *
 226  * Arguments:   @const char *name@ = name of the value being searched for
 227  *              @mp *d@ = destination for resulting integer
 228  *              @mp *m@ = start value to pass to stepper
 229  *              @pgen_proc *event@ = event handler function
 230  *              @void *ectx@ = context argument for event andler
 231  *              @unsigned steps@ = number of steps to take in search
 232  *              @pgen_proc *step@ = stepper function to use
 233  *              @void *sctx@ = context argument for stepper
 234  *              @unsigned tests@ = number of tests to make
 235  *              @pgen_proc *test@ = tester function to use
 236  *              @void *tctx@ = context argument for tester
 237  *
 238  * Returns:     If successful, @PGEN_DONE@; otherwise @PGEN_ABORT@.
 239  *
 240  * Use:         A generalized prime-number search skeleton.  Yes, that's a
 241  *              scary number of arguments.
 242  */
 243
 244 extern mp *pgen(const char */*name*/, mp */*d*/, mp */*m*/,
 245                 pgen_proc */*event*/, void */*ectx*/,
 246                 unsigned /*steps*/, pgen_proc */*step*/, void */*sctx*/,
 247                 unsigned /*tests*/, pgen_proc */*test*/, void */*tctx*/);
 248
 249 /*----- That's all, folks -------------------------------------------------*/
 250
 251 #ifdef __cplusplus
 252   }
 253 #endif
 254
 255 #endif