/* -*-c-*-
*
- * $Id: limlee.c,v 1.4 2000/08/15 21:45:05 mdw Exp $
+ * $Id: limlee.c,v 1.5 2000/08/18 19:16:51 mdw Exp $
*
* Generate Lim-Lee primes
*
/*----- Revision history --------------------------------------------------*
*
* $Log: limlee.c,v $
+ * Revision 1.5 2000/08/18 19:16:51 mdw
+ * New stepper interface for constructing Lim-Lee primes.
+ *
* Revision 1.4 2000/08/15 21:45:05 mdw
* Use the new trial division equipment in pfilt. This gives a 10%
* performance improvement in dsa-gen.t.
#include "mpmul.h"
#include "mprand.h"
#include "pgen.h"
-#include "primorial.h"
#include "rabin.h"
-/*----- Main code ---------------------------------------------------------*/
+/*----- Stepping through combinations -------------------------------------*/
-/* --- @limlee@ --- *
+/* --- @comb_init@ --- *
*
- * Arguments: @const char *name@ = pointer to name root
- * @mp *d@ = pointer to destination integer
- * @mp *newp@ = how to generate factor primes
- * @unsigned ql@ = size of individual factors
- * @unsigned pl@ = size of large prime
- * @grand *r@ = a random number source
- * @unsigned on@ = number of outer attempts to make
- * @pgen_proc *oev@ = outer event handler function
- * @void *oec@ = argument for the outer event handler
- * @pgen_proc *iev@ = inner event handler function
- * @void *iec@ = argument for the inner event handler
- * @size_t *nf@, @mp ***f@ = output array for factors
+ * Arguments: @octet *c@ = pointer to byte-flag array
+ * @unsigned n@ = number of items in the array
+ * @unsigned r@ = number of desired items
*
- * Returns: A Lim-Lee prime, or null if generation failed.
+ * Returns: ---
*
- * Use: Generates Lim-Lee primes. A Lim-Lee prime %$p$% is one which
- * satisfies %$p = 2 \prod_i q_i + 1$%, where all of the %$q_i$%
- * are large enough to resist square-root discrete log
- * algorithms.
- *
- * If we succeed, and @f@ is non-null, we write the array of
- * factors chosen to @f@ for the benefit of the caller.
+ * Use: Initializes a byte-flag array which, under the control of
+ * @comb_next@, will step through all combinations of @r@ chosen
+ * elements.
*/
static void comb_init(octet *c, unsigned n, unsigned r)
memset(c + (n - r), 1, r);
}
+/* --- @comb_next@ --- *
+ *
+ * Arguments: @octet *c@ = pointer to byte-flag array
+ * @unsigned n@ = number of items in the array
+ * @unsigned r@ = number of desired items
+ *
+ * Returns: Nonzero if another combination was returned, zero if we've
+ * reached the end.
+ *
+ * Use: Steps on to the next combination in sequence.
+ */
+
static int comb_next(octet *c, unsigned n, unsigned r)
{
unsigned g = 0;
return (1);
}
+/*----- Default prime generator -------------------------------------------*/
+
+static void llgen(limlee_factor *f, unsigned pl, limlee_stepctx *l)
+{
+ pgen_filterctx pf;
+ rabin r;
+ mp *p;
+
+again:
+ p = mprand(l->newp, pl, l->r, 1);
+ pf.step = 2;
+ p = pgen(l->d.buf, p, p, l->iev, l->iec, 0, pgen_filter, &pf,
+ rabin_iters(pl), pgen_test, &r);
+ if (!p)
+ goto again;
+ f->p = p;
+}
+
+static void llfree(limlee_factor *f, limlee_stepctx *l)
+{
+ if (f->p)
+ mp_drop(f->p);
+}
+
+static const limlee_primeops primeops_simple = { llgen, llfree };
+
+/*----- Lim-Lee stepper ---------------------------------------------------*/
+
+/* --- @init@ --- *
+ *
+ * Arguments: @pgen_event *ev@ = pointer to event block
+ * @limlee_stepctx *l@ = pointer to Lim-Lee context
+ *
+ * Returns: A @PGEN@ result code.
+ *
+ * Use: Initializes the stepper.
+ */
+
+static int init(pgen_event *ev, limlee_stepctx *l)
+{
+ size_t i;
+ unsigned qql;
+
+ /* --- First of all, decide on a number of factors to make --- */
+
+ l->nf = l->pl / l->ql;
+ qql = l->pl % l->ql;
+ if (!l->nf)
+ return (PGEN_ABORT);
+ else if (qql && l->nf > 1) {
+ l->nf--;
+ qql += l->ql;
+ }
+
+ /* --- Now decide on how many primes I'll actually generate --- *
+ *
+ * The formula %$m = \max(3 n + 5, 25)$% comes from GPG's prime generation
+ * library.
+ */
+
+ l->poolsz = l->nf * 3 + 5;
+ if (l->poolsz < 25)
+ l->poolsz = 25;
+
+ /* --- Allocate and initialize the various tables --- */
+
+ l->c = xmalloc(l->poolsz);
+ l->v = xmalloc(l->poolsz * sizeof(limlee_factor));
+ comb_init(l->c, l->poolsz, l->nf);
+ for (i = 0; i < l->poolsz; i++)
+ l->v[i].p = 0;
+
+ /* --- Other bits of initialization --- */
+
+ l->seq = 0;
+ l->r = ev->r;
+ dstr_create(&l->d);
+ if (!l->pops) {
+ l->pops = &primeops_simple;
+ l->pc = 0;
+ }
+
+ /* --- Find a big prime --- */
+
+ if (!qql)
+ l->qq.p = 0;
+ else {
+ dstr_putf(&l->d, "%s*", ev->name);
+ l->pops->pgen(&l->qq, qql, l);
+ }
+
+ return (PGEN_TRY);
+}
+
+/* --- @next@ --- *
+ *
+ * Arguments: @int rq@ = request which triggered this call
+ * @pgen_event *ev@ = pointer to event block
+ * @limlee_stepctx *l@ = pointer to Lim-Lee context
+ *
+ * Returns: A @PGEN@ result code.
+ *
+ * Use: Initializes the stepper.
+ */
+
+static int next(int rq, pgen_event *ev, limlee_stepctx *l)
+{
+ mp *p;
+ int rc;
+
+ if (ev->m)
+ mp_drop(ev->m);
+ l->r = ev->r;
+
+ for (;;) {
+ size_t i;
+ mpmul mm = MPMUL_INIT;
+
+ /* --- Step on to next combination --- */
+
+ if (rq == PGEN_TRY && !comb_next(l->c, l->poolsz, l->nf)) {
+ for (i = 0; i < l->poolsz; i++) {
+ l->pops->pfree(&l->v[i], l);
+ l->v[i].p = 0;
+ }
+ }
+ rq = PGEN_TRY; /* For next time through */
+
+ /* --- Gather up some factors --- */
+
+ if (l->qq.p)
+ mpmul_add(&mm, l->qq.p);
+ for (i = 0; i < l->poolsz; i++) {
+ if (!l->c[i])
+ continue;
+ if (!l->v[i].p) {
+ DRESET(&l->d);
+ dstr_putf(&l->d, "%s_%lu", ev->name, l->seq++);
+ l->pops->pgen(&l->v[i], l->ql, l);
+ }
+ mpmul_add(&mm, l->v[i].p);
+ }
+
+ /* --- Check it for small factors --- */
+
+ p = mpmul_done(&mm);
+ p = mp_lsl(p, p, 1);
+ p->v[0] |= 1;
+ if ((rc = pfilt_smallfactor(p)) != PGEN_FAIL)
+ break;
+ mp_drop(p);
+ }
+
+ ev->m = p;
+ return (rc);
+}
+
+/* --- @done@ --- *
+ *
+ * Arguments: @pgen_event *ev@ = pointer to event block
+ * @limlee_stepctx *l@ = pointer to Lim-Lee context
+ *
+ * Returns: A @PGEN@ result code.
+ *
+ * Use: Finalizes the stepper. The output values in the context
+ * take on their final results; other resources are discarded.
+ */
+
+static int done(pgen_event *ev, limlee_stepctx *l)
+{
+ size_t i, j;
+ limlee_factor *v;
+
+ /* --- If an output vector of factors is wanted, produce one --- */
+
+ if (!(l->f & LIMLEE_KEEPFACTORS))
+ v = 0;
+ else {
+ if (l->qq.p)
+ l->nf++;
+ v = xmalloc(l->nf * sizeof(limlee_factor));
+ }
+
+ for (i = 0, j = 0; i < l->poolsz; i++) {
+ if (v && l->c[i])
+ v[j++] = l->v[i];
+ else if (l->v[i].p)
+ l->pops->pfree(&l->v[i], l);
+ }
+
+ if (l->qq.p) {
+ if (v)
+ v[j++] = l->qq;
+ else
+ l->pops->pfree(&l->qq, l);
+ }
+
+ xfree(l->v);
+ l->v = v;
+
+ /* --- Free other resources --- */
+
+ xfree(l->c);
+ dstr_destroy(&l->d);
+
+ /* --- Done --- */
+
+ return (PGEN_DONE);
+}
+
+/* --- @limlee_step@ --- */
+
+int limlee_step(int rq, pgen_event *ev, void *p)
+{
+ limlee_stepctx *l = p;
+ int rc;
+
+ switch (rq) {
+ case PGEN_BEGIN:
+ if ((rc = init(ev, l)) != PGEN_TRY)
+ return (rc);
+ case PGEN_TRY:
+ return (next(rq, ev, l));
+ case PGEN_DONE:
+ return (done(ev, l));
+ }
+ return (PGEN_ABORT);
+}
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @limlee@ --- *
+ *
+ * Arguments: @const char *name@ = pointer to name root
+ * @mp *d@ = pointer to destination integer
+ * @mp *newp@ = how to generate factor primes
+ * @unsigned ql@ = size of individual factors
+ * @unsigned pl@ = size of large prime
+ * @grand *r@ = a random number source
+ * @unsigned on@ = number of outer attempts to make
+ * @pgen_proc *oev@ = outer event handler function
+ * @void *oec@ = argument for the outer event handler
+ * @pgen_proc *iev@ = inner event handler function
+ * @void *iec@ = argument for the inner event handler
+ * @size_t *nf@, @mp ***f@ = output array for factors
+ *
+ * Returns: A Lim-Lee prime, or null if generation failed.
+ *
+ * Use: Generates Lim-Lee primes. A Lim-Lee prime %$p$% is one which
+ * satisfies %$p = 2 \prod_i q_i + 1$%, where all of the %$q_i$%
+ * are large enough to resist square-root discrete log
+ * algorithms.
+ *
+ * If we succeed, and @f@ is non-null, we write the array of
+ * factors chosen to @f@ for the benefit of the caller.
+ */
+
mp *limlee(const char *name, mp *d, mp *newp,
unsigned ql, unsigned pl, grand *r,
unsigned on, pgen_proc *oev, void *oec,
pgen_proc *iev, void *iec,
size_t *nf, mp ***f)
{
+#ifdef notdef
dstr dn = DSTR_INIT;
unsigned qql;
mp *qq = 0;
pf.step = 2;
if (qql) {
- dstr_putf(&dn, "%s [+]", name);
+ dstr_putf(&dn, "%s*", name);
qq = mprand(d, qql, r, 1);
qq = pgen(dn.buf, qq, qq, iev, iec,
0, pgen_filter, &pf, rabin_iters(qql), pgen_test, &rb);
mp *z;
DRESET(&dn);
- dstr_putf(&dn, "%s [%lu] = ", name, seq++);
+ dstr_putf(&dn, "%s_%lu] = ", name, seq++);
z = mprand(newp, ql, ev.r, 1);
z = pgen(dn.buf, z, z, iev, iec,
0, pgen_filter, &pf, rabin_iters(ql), pgen_test, &rb);
xfree(c);
dstr_destroy(&dn);
return (0);
+#else
+ limlee_stepctx l;
+ rabin rr;
+
+ l.f = 0; if (f) l.f |= LIMLEE_KEEPFACTORS;
+ l.newp = newp;
+ l.pl = pl; l.ql = ql;
+ l.pops = 0;
+ l.iev = iev;
+ l.iec = iec;
+
+ d = pgen(name, d, 0, oev, oec, on, limlee_step, &l,
+ rabin_iters(pl), pgen_test, &rr);
+
+ if (f) {
+ mp **v;
+ size_t i;
+ v = xmalloc(l.nf * sizeof(mp *));
+ for (i = 0; i < l.nf; i++)
+ v[i] = l.v[i].p;
+ xfree(l.v);
+ *f = v;
+ *nf = l.nf;
+ }
+
+ return (d);
+#endif
}
/*----- That's all, folks -------------------------------------------------*/
/* -*-c-*-
*
- * $Id: limlee.h,v 1.1 2000/07/09 21:30:58 mdw Exp $
+ * $Id: limlee.h,v 1.2 2000/08/18 19:16:51 mdw Exp $
*
* Generate Lim-Lee primes
*
/*----- Revision history --------------------------------------------------*
*
* $Log: limlee.h,v $
+ * Revision 1.2 2000/08/18 19:16:51 mdw
+ * New stepper interface for constructing Lim-Lee primes.
+ *
* Revision 1.1 2000/07/09 21:30:58 mdw
* Lim-Lee prime generation.
*
# include "pgen.h"
#endif
+/*----- Data structures ---------------------------------------------------*/
+
+typedef struct limlee_factor {
+ mp *p; /* The actual prime */
+ unsigned tag; /* A tag, usable by the generator */
+ void *more; /* Pointer to more data */
+} limlee_factor;
+
+typedef struct limlee_stepctx {
+
+ /* --- To be initialized by the caller --- */
+
+ unsigned f; /* Various useful flags */
+ mp *newp; /* Initial valid for new primes */
+ unsigned ql, pl; /* Size of factors and result */
+ const struct limlee_primeops *pops; /* Pointer to generator ops */
+ void *pc; /* Context ptr for generator ops */
+ pgen_proc *iev; /* Event handler for inner @pgen@ */
+ void *iec; /* Context for inner @pgen@ */
+
+ /* --- Output values --- */
+
+ size_t nf; /* Number of factors wanted */
+ limlee_factor *v; /* Vector of factors */
+
+ /* --- Maintained internally --- */
+
+ octet *c; /* Combination byte-flag vector */
+ grand *r; /* Random number generator */
+ unsigned long seq; /* Sequence number for primes */
+ size_t poolsz; /* Size of the small-prime pool */
+ dstr d; /* String for subprime name */
+ limlee_factor qq; /* Big prime to pick up slack */
+
+} limlee_stepctx;
+
+typedef struct limlee_primeops {
+ void (*pgen)(limlee_factor */*f*/, unsigned /*pl*/, limlee_stepctx */*l*/);
+ void (*pfree)(limlee_factor */*f*/, limlee_stepctx */*l*/);
+} limlee_primeops;
+
+/* --- Flags --- */
+
+enum {
+ LIMLEE_KEEPFACTORS = 1
+};
+
+/*----- The Lim-Lee stepper function --------------------------------------*/
+
+extern int limlee_step(int /*rq*/, pgen_event */*ev*/, void */*p*/);
+
/*----- Functions provided ------------------------------------------------*/
/* --- @limlee@ --- *
projects / u / mdw / catacomb / commitdiff