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 /* --- @pgen_bailliepswtest@ --- *
 170  *
 171  * Runs the Baillie--PSW primality test.  The context block is ignored.  The
 172  * number of tests must be 2 (= @PGEN_BAILLIEPSWNTESTS@).
 173  */
 174
 175 extern pgen_proc pgen_bailliepswtest;
 176 #define PGEN_BAILLIEPSWNTESTS 2
 177
 178 /*----- Simultaneous primality checking -----------------------------------*/
 179
 180 typedef struct pgen_simulprime {
 181   mp *mul, *add;                        /* Arguments from the client */
 182   unsigned f;                           /* Flags, set by client, changed */
 183 #define PGENF_KEEP 1u                   /*   Keep this prime's value */
 184 #define PGENF_JUMP 8u                   /*   Use jump table, not stepping */
 185   pfilt p;                              /* This prime's filter */
 186   rabin r;                              /* Rabin testing context */
 187   union {
 188     mpw step;                           /* The simple step to use */
 189     pfilt *jump;                        /* The jump to move by */
 190     mp *x;                              /* The result, if wanted */
 191   } u;
 192 } pgen_simulprime;
 193
 194 typedef struct pgen_simulctx {
 195   pgen_simulprime *v;                   /* Vector of related primes */
 196   unsigned n;                           /* Size of the vector */
 197   mp *step;                             /* Basic stepping value */
 198 } pgen_simulctx;
 199
 200 /* --- @pgen_simulstep@ --- *
 201  *
 202  * Step a collection of numbers simultaneously.
 203  */
 204
 205 extern pgen_proc pgen_simulstep;
 206
 207 /* --- @pgen_simultest@ --- *
 208  *
 209  * Test a collection of numbers simultaneously.
 210  */
 211
 212 extern pgen_proc pgen_simultest;
 213
 214 /* --- @pgen_simulbailliepswtest@ --- *
 215  *
 216  * Test a collection of numbers simultaneously using Baillie--PSW.
 217  */
 218
 219 extern pgen_proc pgen_simulbailliepswtest;
 220
 221 /*----- Miscellaneous steppers and testers --------------------------------*/
 222
 223 typedef struct pgen_gcdstepctx {
 224   pfilt p, jp;                          /* Prime filter and step filter */
 225   mp *q, *jq;                           /* %$p - 1$%, and a step value*/
 226   mp *r;                                /* Other argument for GCD */
 227   mp *g;                                /* GCD output (must be inited) */
 228   mp *max;                              /* Maximum permissible GCD */
 229 } pgen_gcdstepctx;
 230
 231 /* --- @pgen_gcdstep@ --- *
 232  *
 233  * Steps @p@ and @q@, until @p@ has no small factors, and
 234  * %$\gcd(p, r) \le max$%.
 235  */
 236
 237 extern pgen_proc pgen_gcdstep;
 238
 239 /*----- Standard event handlers -------------------------------------------*/
 240
 241 /* --- @pgen_evspin@ --- *
 242  *
 243  * Displays a spinning baton to show progress.
 244  */
 245
 246 extern pgen_proc pgen_evspin;
 247
 248 /* --- @pgen_ev@ --- *
 249  *
 250  * Traditional event handler, shows dots for each test.
 251  */
 252
 253 extern pgen_proc pgen_ev;
 254
 255 /* --- @pgen_subev@ --- *
 256  *
 257  * Subsidiary event handler, mainly for Lim-Lee searches and so on.
 258  */
 259
 260 extern pgen_proc pgen_subev;
 261
 262 /*----- The main driver ---------------------------------------------------*/
 263
 264 /* --- @pgen@ --- *
 265  *
 266  * Arguments:   @const char *name@ = name of the value being searched for
 267  *              @mp *d@ = destination for resulting integer
 268  *              @mp *m@ = start value to pass to stepper
 269  *              @pgen_proc *event@ = event handler function
 270  *              @void *ectx@ = context argument for event andler
 271  *              @unsigned steps@ = number of steps to take in search
 272  *              @pgen_proc *step@ = stepper function to use
 273  *              @void *sctx@ = context argument for stepper
 274  *              @unsigned tests@ = number of tests to make
 275  *              @pgen_proc *test@ = tester function to use
 276  *              @void *tctx@ = context argument for tester
 277  *
 278  * Returns:     The resulting value, or null.
 279  *
 280  * Use:         A generalized prime-number search skeleton.  Yes, that's a
 281  *              scary number of arguments.
 282  */
 283
 284 extern mp *pgen(const char */*name*/, mp */*d*/, mp */*m*/,
 285                 pgen_proc */*event*/, void */*ectx*/,
 286                 unsigned /*steps*/, pgen_proc */*step*/, void */*sctx*/,
 287                 unsigned /*tests*/, pgen_proc */*test*/, void */*tctx*/);
 288
 289 /* --- @pgen_granfrob@ --- *
 290  *
 291  * Arguments:   @mp *n@ = an integer to test
 292  *              @int a, b@ = coefficients; if @a@ is zero then choose
 293  *                      automatically
 294  *
 295  * Returns:     One of the @PGEN_...@ codes.
 296  *
 297  * Use:         Performs a quadratic version of Grantham's Frobenius
 298  *              primality test, which is a simple extension of the standard
 299  *              Lucas test.
 300  *
 301  *              If %$a^2 - 4 b$% is a perfect square then the test can't
 302  *              work; this function returns @PGEN_ABORT@ under these
 303  *              circumstances.
 304  *
 305  *              If @a@ is zero on entry, then the function will choose
 306  *              suitable parameters deterministically -- i.e., it always
 307  *              chooses the same parameters for a given %$n$%.
 308  */
 309
 310 extern int pgen_granfrob(mp */*n*/, int /*a*/, int /*b*/);
 311
 312 /* --- @pgen_primep@ --- *
 313  *
 314  * Arguments:   @mp *p@ = a number to check
 315  *              @grand *gr@ = a random number source
 316  *
 317  * Returns:     Nonzero if @p@ is really prime.
 318  */
 319
 320 extern int pgen_primep(mp */*p*/, grand */*gr*/);
 321
 322 /*----- That's all, folks -------------------------------------------------*/
 323
 324 #ifdef __cplusplus
 325   }
 326 #endif
 327
 328 #endif