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

   1 /* -*-c-*-
   2  *
   3  * Prime generation glue
   4  *
   5  * (c) 1999 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 #ifndef CATACOMB_PGEN_H
  29 #define CATACOMB_PGEN_H
  30
  31 #ifdef __cplusplus
  32   extern "C" {
  33 #endif
  34
  35 /*----- Header files ------------------------------------------------------*/
  36
  37 #ifndef CATACOMB_GRAND_H
  38 #  include "grand.h"
  39 #endif
  40
  41 #ifndef CATACOMB_MP_H
  42 #  include "mp.h"
  43 #endif
  44
  45 #ifndef CATACOMB_PFILT_H
  46 #  include "pfilt.h"
  47 #endif
  48
  49 #ifndef CATACOMB_RABIN_H
  50 #  include "rabin.h"
  51 #endif
  52
  53 /*----- Event handling ----------------------------------------------------*
  54  *
  55  * Different programs and architectures will want to show progress of prime
  56  * searches and similar processes in different ways.  Of course, for simple
  57  * searches, it's possible to use the @pfilt@ and @rabin@ functions and
  58  * maintain control over the general control flow throughout the search.
  59  *
  60  * For more complex cases, this sort of control is undesirable.  It's
  61  * possible to specify an event handler which is informed in abstract about
  62  * the search.  The event handler can also request the search be aborted.
  63  */
  64
  65 /* --- Event code constants --- *
  66  *
  67  * You're allowed to rely on the values of @PGEN_DONE@ and @PGEN_ABORT@.
  68  */
  69
  70 enum {
  71   PGEN_BEGIN = 1,                       /* Search for value begins */
  72   PGEN_TRY,                             /* A new candidate has appeared */
  73   PGEN_FAIL,                            /* The candidate failed the test */
  74   PGEN_PASS,                            /* The candidate passed a test */
  75   PGEN_DONE = 0,                        /* A good value has been found */
  76   PGEN_ABORT = -1                       /* The search has been aborted */
  77 };
  78
  79 /* --- Event information --- *
  80  *
  81  * Note that the pseudorandom number generator supplied is not
  82  * cryptographically strong.
  83  */
  84
  85 typedef struct pgen_event {
  86   const char *name;                     /* Which quantity is being found */
  87   mp *m;                                /* Current value under test */
  88   unsigned steps;                       /* Number of candidates left */
  89   unsigned tests;                       /* Tests left before passing */
  90   grand *r;                             /* Source of random numbers */
  91 } pgen_event;
  92
  93 /*----- Prime search parameters -------------------------------------------*
  94  *
  95  * The prime search is parameterized in a large number of ways, although this
  96  * isn't so much of a surprise given the different sorts of properties
  97  * required from prime numbers in cryptographic applications.
  98  *
  99  * There are two main things which need to be configured: stepping, and
 100  * testing.  (Filtering is done as part of stepping.)
 101  *
 102  * The functions here provide a toolkit for constructing stepping and testing
 103  * routines.  In a lot of cases, the functions can be used directly; in
 104  * others, simple bits of glue need be written.
 105  *
 106  * Two types of functions are defined: steppers and testers, but their
 107  * interfaces are substantially similar.  Each is given a request code, a
 108  * context block and an event block.  It is meant to update its context and
 109  * the event block and return an event code.
 110  *
 111  * A call with a request of @PGEN_BEGIN@ asks the stepper or tester to
 112  * initialize itself using the information in its event block and context.  A
 113  * return of @PGEN_FAIL@ reports an immediate failure; @PGEN_ABORT@ reports a
 114  * fatal problem; @PGEN_DONE@ reports immediate success.  @PGEN_TRY@ reports
 115  * successful initialization and requests test iterations.
 116  *
 117  * A call to a stepper with a request of @PGEN_TRY@ asks it to step to the
 118  * next possible candidate, replacing the value @m@ in the event block with
 119  * the new candidate.  A call to a tester with a request of @PGEN_TRY@
 120  * runs one pass of the test.  It should return @PGEN_FAIL@ to report a
 121  * failure, @PGEN_PASS@ to report a success and request another iteration,
 122  * @PGEN_DONE@ to report final acceptance and @PGEN_ABORT@ to terminate the
 123  * search unsuccessfully.  Note that even if the search is aborted, a
 124  * shutdown request is still made.
 125  *
 126  * A call with a request of @PGEN_DONE@ closes down the stepper or tester.
 127  * After a successful initialization (i.e., a return of something other than
 128  * @PGEN_ABORT@), a shutdown call is guaranteed.  The return code is ignored.
 129  */
 130
 131 typedef int pgen_proc(int /*rq*/, pgen_event */*ev*/, void */*p*/);
 132
 133 /*----- Simple handler functions ------------------------------------------*/
 134
 135 /* --- @pgen_filter@ --- *
 136  *
 137  * A prime generation context contains the information required for the
 138  * simple prime filter and tester presented here.
 139  */
 140
 141 typedef struct pgen_filterctx {
 142   unsigned step;                        /* Step size (set by client) */
 143   pfilt f;                              /* The rapid prime filter */
 144 } pgen_filterctx;
 145
 146 extern pgen_proc pgen_filter;
 147
 148 /* --- @pgen_jump@ --- *
 149  *
 150  * Similar to the standard @pgen_filter@, but jumps in large steps rather
 151  * than small ones.
 152  */
 153
 154 typedef struct pgen_jumpctx {
 155   const pfilt *j;
 156   pfilt f;
 157 } pgen_jumpctx;
 158
 159 extern pgen_proc pgen_jump;
 160
 161 /* --- @pgen_test@ --- *
 162  *
 163  * Runs the Rabin-Miller primality test.  The context block is simply a
 164  * @rabin@ context.
 165  */
 166
 167 extern pgen_proc pgen_test;
 168
 169 /*----- Simultaneous primality checking -----------------------------------*/
 170
 171 typedef struct pgen_simulprime {
 172   mp *mul, *add;                        /* Arguments from the client */
 173   unsigned f;                           /* Flags, set by client, changed */
 174 #define PGENF_KEEP 1u                   /*   Keep this prime's value */
 175 #define PGENF_JUMP 8u                   /*   Use jump table, not stepping */
 176   pfilt p;                              /* This prime's filter */
 177   rabin r;                              /* Rabin testing context */
 178   union {
 179     mpw step;                           /* The simple step to use */
 180     pfilt *jump;                        /* The jump to move by */
 181     mp *x;                              /* The result, if wanted */
 182   } u;
 183 } pgen_simulprime;
 184
 185 typedef struct pgen_simulctx {
 186   pgen_simulprime *v;                   /* Vector of related primes */
 187   unsigned n;                           /* Size of the vector */
 188   mp *step;                             /* Basic stepping value */
 189 } pgen_simulctx;
 190
 191 /* --- @pgen_simulstep@ --- *
 192  *
 193  * Step a collection of numbers simultaneously.
 194  */
 195
 196 extern pgen_proc pgen_simulstep;
 197
 198 /* --- @pgen_simultest@ --- *
 199  *
 200  * Test a collection of numbers simultaneously.
 201  */
 202
 203 extern pgen_proc pgen_simultest;
 204
 205 /*----- Miscellaneous steppers and testers --------------------------------*/
 206
 207 typedef struct pgen_gcdstepctx {
 208   pfilt p, jp;                          /* Prime filter and step filter */
 209   mp *q, *jq;                           /* %$p - 1$%, and a step value*/
 210   mp *r;                                /* Other argument for GCD */
 211   mp *g;                                /* GCD output (must be inited) */
 212   mp *max;                              /* Maximum permissible GCD */
 213 } pgen_gcdstepctx;
 214
 215 /* --- @pgen_gcdstep@ --- *
 216  *
 217  * Steps @p@ and @q@, until @p@ has no small factors, and
 218  * %$\gcd(p, r) \le max$%.
 219  */
 220
 221 extern pgen_proc pgen_gcdstep;
 222
 223 /*----- Standard event handlers -------------------------------------------*/
 224
 225 /* --- @pgen_evspin@ --- *
 226  *
 227  * Displays a spinning baton to show progress.
 228  */
 229
 230 extern pgen_proc pgen_evspin;
 231
 232 /* --- @pgen_ev@ --- *
 233  *
 234  * Traditional event handler, shows dots for each test.
 235  */
 236
 237 extern pgen_proc pgen_ev;
 238
 239 /* --- @pgen_subev@ --- *
 240  *
 241  * Subsidiary event handler, mainly for Lim-Lee searches and so on.
 242  */
 243
 244 extern pgen_proc pgen_subev;
 245
 246 /*----- The main driver ---------------------------------------------------*/
 247
 248 /* --- @pgen@ --- *
 249  *
 250  * Arguments:   @const char *name@ = name of the value being searched for
 251  *              @mp *d@ = destination for resulting integer
 252  *              @mp *m@ = start value to pass to stepper
 253  *              @pgen_proc *event@ = event handler function
 254  *              @void *ectx@ = context argument for event andler
 255  *              @unsigned steps@ = number of steps to take in search
 256  *              @pgen_proc *step@ = stepper function to use
 257  *              @void *sctx@ = context argument for stepper
 258  *              @unsigned tests@ = number of tests to make
 259  *              @pgen_proc *test@ = tester function to use
 260  *              @void *tctx@ = context argument for tester
 261  *
 262  * Returns:     The resulting value, or null.
 263  *
 264  * Use:         A generalized prime-number search skeleton.  Yes, that's a
 265  *              scary number of arguments.
 266  */
 267
 268 extern mp *pgen(const char */*name*/, mp */*d*/, mp */*m*/,
 269                 pgen_proc */*event*/, void */*ectx*/,
 270                 unsigned /*steps*/, pgen_proc */*step*/, void */*sctx*/,
 271                 unsigned /*tests*/, pgen_proc */*test*/, void */*tctx*/);
 272
 273 /* --- @pgen_granfrob@ --- *
 274  *
 275  * Arguments:   @mp *n@ = an integer to test
 276  *              @int a, b@ = coefficients; if @a@ is zero then choose
 277  *                      automatically
 278  *
 279  * Returns:     One of the @PGEN_...@ codes.
 280  *
 281  * Use:         Performs a quadratic version of Grantham's Frobenius
 282  *              primality test, which is a simple extension of the standard
 283  *              Lucas test.
 284  *
 285  *              If %$a^2 - 4 b$% is a perfect square then the test can't
 286  *              work; this function returns @PGEN_ABORT@ under these
 287  *              circumstances.
 288  *
 289  *              If @a@ is zero on entry, then the function will choose
 290  *              suitable parameters deterministically -- i.e., it always
 291  *              chooses the same parameters for a given %$n$%.
 292  */
 293
 294 extern int pgen_granfrob(mp */*n*/, int /*a*/, int /*b*/);
 295
 296 /* --- @pgen_primep@ --- *
 297  *
 298  * Arguments:   @mp *p@ = a number to check
 299  *              @grand *gr@ = a random number source
 300  *
 301  * Returns:     Nonzero if @p@ is really prime.
 302  */
 303
 304 extern int pgen_primep(mp */*p*/, grand */*gr*/);
 305
 306 /*----- That's all, folks -------------------------------------------------*/
 307
 308 #ifdef __cplusplus
 309   }
 310 #endif
 311
 312 #endif