From 10217a5c148f63def6fc564960a9f28ae42d52dc Mon Sep 17 00:00:00 2001 From: mdw Date: Fri, 18 Aug 2000 19:16:51 +0000 Subject: [PATCH] New stepper interface for constructing Lim-Lee primes. --- limlee.c | 338 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----- limlee.h | 56 ++++++++++- 2 files changed, 367 insertions(+), 27 deletions(-) diff --git a/limlee.c b/limlee.c index 45f579d..60f6bb5 100644 --- a/limlee.c +++ b/limlee.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,9 @@ /*----- 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. @@ -55,35 +58,21 @@ #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) @@ -92,6 +81,18 @@ 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; @@ -129,12 +130,270 @@ static int comb_next(octet *c, unsigned n, unsigned r) 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; @@ -188,7 +447,7 @@ mp *limlee(const char *name, mp *d, mp *newp, 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); @@ -216,7 +475,7 @@ again: 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); @@ -336,6 +595,33 @@ fail: 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 -------------------------------------------------*/ diff --git a/limlee.h b/limlee.h index d6fcc4b..bccfccb 100644 --- a/limlee.h +++ b/limlee.h @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,9 @@ /*----- 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. * @@ -56,6 +59,57 @@ # 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@ --- * -- 2.11.0