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   dstr d;                               /* String for subprime name */
  81   limlee_factor qq;                     /* Big prime to pick up slack */
  82
  83 } limlee_stepctx;
  84
  85 typedef struct limlee_primeops {
  86   void (*pgen)(limlee_factor */*f*/, unsigned /*pl*/, limlee_stepctx */*l*/);
  87   void (*pfree)(limlee_factor */*f*/, limlee_stepctx */*l*/);
  88 } limlee_primeops;
  89
  90 /* --- Flags --- */
  91
  92 #define LIMLEE_KEEPFACTORS 1u
  93
  94 /*----- The Lim-Lee stepper function --------------------------------------*/
  95
  96 extern pgen_proc limlee_step;
  97
  98 /*----- Functions provided ------------------------------------------------*/
  99
 100 /* --- @limlee@ --- *
 101  *
 102  * Arguments:   @const char *name@ = pointer to name root
 103  *              @mp *d@ = pointer to destination integer
 104  *              @mp *newp@ = how to generate factor primes
 105  *              @unsigned ql@ = size of individual factors
 106  *              @unsigned pl@ = size of large prime
 107  *              @grand *r@ = a random number source
 108  *              @unsigned on@ = number of outer attempts to make
 109  *              @pgen_proc *oev@ = outer event handler function
 110  *              @void *oec@ = argument for the outer event handler
 111  *              @pgen_proc *iev@ = inner event handler function
 112  *              @void *iec@ = argument for the inner event handler
 113  *              @size_t *nf@, @mp ***f@ = output array for factors
 114  *
 115  * Returns:     A Lim-Lee prime, or null if generation failed.
 116  *
 117  * Use:         Generates Lim-Lee primes.  A Lim-Lee prime %$p$% is one which
 118  *              satisfies %$p = 2 \prod_i q_i + 1$%, where all of the %$q_i$%
 119  *              are large enough to resist square-root discrete log
 120  *              algorithms.
 121  *
 122  *              If we succeed, and @f@ is non-null, we write the array of
 123  *              factors chosen to @f@ for the benefit of the caller.
 124  */
 125
 126 extern mp *limlee(const char */*name*/, mp */*d*/, mp */*newp*/,
 127                   unsigned /*ql*/, unsigned /*pl*/, grand */*r*/,
 128                   unsigned /*on*/, pgen_proc */*oev*/, void */*oec*/,
 129                   pgen_proc */*iev*/, void */*iec*/,
 130                   size_t */*nf*/, mp ***/*f*/);
 131
 132 /*----- That's all, folks -------------------------------------------------*/
 133
 134 #ifdef __cplusplus
 135   }
 136 #endif
 137
 138 #endif