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

   1 /* -*-c-*-
   2  *
   3  * Generate Lim-Lee primes
   4  *
   5  * (c) 2000 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_LIMLEE_H
  29 #define CATACOMB_LIMLEE_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_PGEN_H
  46 #  include "pgen.h"
  47 #endif
  48
  49 /*----- Data structures ---------------------------------------------------*/
  50
  51 typedef struct limlee_factor {
  52   mp *p;                                /* The actual prime */
  53   unsigned tag;                         /* A tag, usable by the generator */
  54   void *more;                           /* Pointer to more data */
  55 } limlee_factor;
  56
  57 typedef struct limlee_stepctx {
  58
  59   /* --- To be initialized by the caller --- */
  60
  61   unsigned f;                           /* Various useful flags */
  62   mp *newp;                             /* Initial valid for new primes */
  63   unsigned ql, pl;                      /* Size of factors and result */
  64   const struct limlee_primeops *pops;   /* Pointer to generator ops */
  65   void *pc;                             /* Context ptr for generator ops */
  66   pgen_proc *iev;                       /* Event handler for inner @pgen@ */
  67   void *iec;                            /* Context for inner @pgen@ */
  68   grand *r;                             /* Random number generator */
  69
  70   /* --- Output values --- */
  71
  72   size_t nf;                            /* Number of factors wanted */
  73   limlee_factor *v;                     /* Vector of factors */
  74
  75   /* --- Maintained internally --- */
  76
  77   octet *c;                             /* Combination byte-flag vector */
  78   unsigned long seq;                    /* Sequence number for primes */
  79   size_t poolsz;                        /* Size of the small-prime pool */
  80   union {
  81     dstr d;                             /* Obsolete; for ABI compat */
  82     struct {
  83       char *name;                       /* Name, for @primeops@ */
  84       int steps, disp;                  /* Track how good @qq@ is */
  85     } s;
  86   } u;
  87   limlee_factor qq;                     /* Big prime to pick up slack */
  88
  89 } limlee_stepctx;
  90
  91 typedef struct limlee_primeops {
  92   void (*pgen)(limlee_factor */*f*/, unsigned /*pl*/, limlee_stepctx */*l*/);
  93   void (*pfree)(limlee_factor */*f*/, limlee_stepctx */*l*/);
  94 } limlee_primeops;
  95
  96 /* --- Flags --- */
  97
  98 #define LIMLEE_KEEPFACTORS 1u
  99
 100 /*----- The Lim-Lee stepper function --------------------------------------*/
 101
 102 extern pgen_proc limlee_step;
 103
 104 /*----- Functions provided ------------------------------------------------*/
 105
 106 /* --- @limlee@ --- *
 107  *
 108  * Arguments:   @const char *name@ = pointer to name root
 109  *              @mp *d@ = pointer to destination integer
 110  *              @mp *newp@ = how to generate factor primes
 111  *              @unsigned ql@ = size of individual factors
 112  *              @unsigned pl@ = size of large prime
 113  *              @grand *r@ = a random number source
 114  *              @unsigned on@ = number of outer attempts to make
 115  *              @pgen_proc *oev@ = outer event handler function
 116  *              @void *oec@ = argument for the outer event handler
 117  *              @pgen_proc *iev@ = inner event handler function
 118  *              @void *iec@ = argument for the inner event handler
 119  *              @size_t *nf@, @mp ***f@ = output array for factors
 120  *
 121  * Returns:     A Lim-Lee prime, or null if generation failed.
 122  *
 123  * Use:         Generates Lim-Lee primes.  A Lim-Lee prime %$p$% is one which
 124  *              satisfies %$p = 2 \prod_i q_i + 1$%, where all of the %$q_i$%
 125  *              are large enough to resist square-root discrete log
 126  *              algorithms.
 127  *
 128  *              If we succeed, and @f@ is non-null, we write the array of
 129  *              factors chosen to @f@ for the benefit of the caller.
 130  */
 131
 132 extern mp *limlee(const char */*name*/, mp */*d*/, mp */*newp*/,
 133                   unsigned /*ql*/, unsigned /*pl*/, grand */*r*/,
 134                   unsigned /*on*/, pgen_proc */*oev*/, void */*oec*/,
 135                   pgen_proc */*iev*/, void */*iec*/,
 136                   size_t */*nf*/, mp ***/*f*/);
 137
 138 /*----- That's all, folks -------------------------------------------------*/
 139
 140 #ifdef __cplusplus
 141   }
 142 #endif
 143
 144 #endif