X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/2f6275469096d6f482a8510de15e5b3402c26b56..07290a455e008c37adc233554eff8ad468608161:/limlee.c diff --git a/limlee.c b/limlee.c index dd03866..b6fc4d6 100644 --- a/limlee.c +++ b/limlee.c @@ -1,13 +1,13 @@ /* -*-c-*- * - * $Id: limlee.c,v 1.3 2000/07/29 09:58:32 mdw Exp $ + * $Id: limlee.c,v 1.9 2004/04/08 01:36:15 mdw Exp $ * * Generate Lim-Lee primes * * (c) 2000 Straylight/Edgeware */ -/*----- Licensing notice --------------------------------------------------* +/*----- Licensing notice --------------------------------------------------* * * This file is part of Catacomb. * @@ -15,33 +15,18 @@ * it under the terms of the GNU Library General Public License as * published by the Free Software Foundation; either version 2 of the * License, or (at your option) any later version. - * + * * Catacomb is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Library General Public License for more details. - * + * * You should have received a copy of the GNU Library General Public * License along with Catacomb; if not, write to the Free * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, * MA 02111-1307, USA. */ -/*----- Revision history --------------------------------------------------* - * - * $Log: limlee.c,v $ - * Revision 1.3 2000/07/29 09:58:32 mdw - * (limlee): Bug fix. Old versions didn't set the filter step if @ql@ was - * an exact divisor of @pl@. - * - * Revision 1.2 2000/07/26 18:00:00 mdw - * No footer line! - * - * Revision 1.1 2000/07/09 21:30:58 mdw - * Lim-Lee prime generation. - * - */ - /*----- Header files ------------------------------------------------------*/ #include @@ -51,35 +36,21 @@ #include "mpmul.h" #include "mprand.h" #include "pgen.h" -#include "primorial.h" #include "rabin.h" -/*----- Main code ---------------------------------------------------------*/ +/*----- Stepping through combinations -------------------------------------*/ -/* --- @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 +/* --- @comb_init@ --- * * - * Returns: A Lim-Lee prime, or null if generation failed. + * Arguments: @octet *c@ = pointer to byte-flag array + * @unsigned n@ = number of items in the array + * @unsigned r@ = number of desired items * - * 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. + * Returns: --- * - * 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) @@ -88,6 +59,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; @@ -125,35 +108,57 @@ static int comb_next(octet *c, unsigned n, unsigned r) return (1); } -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) +/*----- Default prime generator -------------------------------------------*/ + +static void llgen(limlee_factor *f, unsigned pl, limlee_stepctx *l) { - dstr dn = DSTR_INIT; - unsigned qql; - mp *qq = 0; - unsigned nn; - unsigned mm; - mp **v; - octet *c; - unsigned i; - unsigned long seq = 0; - pgen_event ev; - unsigned ntest; - rabin rb; 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) +{ + 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 --- */ - nn = pl/ql; - qql = pl%ql; - if (!nn) - return (0); - else if (qql && nn > 1) { - nn--; - qql += ql; + 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 --- * @@ -162,179 +167,232 @@ mp *limlee(const char *name, mp *d, mp *newp, * library. */ - mm = nn * 3 + 5; - if (mm < 25) - mm = 25; + l->poolsz = l->nf * 3 + 5; + if (l->poolsz < 25) + l->poolsz = 25; - /* --- Now allocate the working memory --- */ + /* --- Allocate and initialize the various tables --- */ - primorial_setup(); - v = xmalloc(mm * sizeof(mp *)); - c = xmalloc(mm); + 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; - /* --- Initialize everything and try to find a prime --- */ + /* --- Other bits of initialization --- */ - ev.name = name; - ev.m = 0; - ev.steps = on; - ev.tests = ntest = rabin_iters(pl); - ev.r = r; + l->seq = 0; + dstr_create(&l->d); + if (!l->pops) { + l->pops = &primeops_simple; + l->pc = 0; + } - if (oev && oev(PGEN_BEGIN, &ev, oec) == PGEN_ABORT) - goto fail; + /* --- Find a big prime --- */ - pf.step = 2; - if (qql) { - 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); + if (!qql) + l->qq.p = 0; + else { + dstr_putf(&l->d, "%s*", ev->name); + l->pops->pgen(&l->qq, qql, l); } -again: - comb_init(c, mm, nn); - for (i = 0; i < mm; i++) - v[i] = 0; + return (PGEN_TRY); +} - /* --- The main combinations loop --- */ +/* --- @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; - do { - mpmul mmul = MPMUL_INIT; + mp_drop(ev->m); - /* --- Multiply a bunch of primes together --- */ + for (;;) { + size_t i; + mpmul mm = MPMUL_INIT; - if (qq) { - mpmul_add(&mmul, qq); + /* --- 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; + } } - for (i = 0; i < mm; i++) { - if (!c[i]) + 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 (!v[i]) { - mp *z; - - DRESET(&dn); - 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); - v[i] = z; + 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(&mmul, v[i]); + mpmul_add(&mm, l->v[i].p); } - /* --- Now do some testing --- */ + /* --- Check it for small factors --- */ - { - mp *p = mpmul_done(&mmul); - mp *g = newp; - int rc; + 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); + } - /* --- Check for small factors --- */ + ev->m = p; + return (rc); +} - p = mp_lsl(p, p, 1); - p = mp_add(p, p, MP_ONE); - mp_gcd(&g, 0, 0, p, primorial); - if (MP_CMP(g, !=, MP_ONE)) { - mp_drop(g); - mp_drop(p); - continue; - } - mp_drop(g); +/* --- @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. + */ - /* --- Send an event out --- */ +static int done(pgen_event *ev, limlee_stepctx *l) +{ + size_t i, j; + limlee_factor *v; - ev.m = p; - if (oev && oev(PGEN_TRY, &ev, oec) == PGEN_ABORT) { - mp_drop(p); - goto fail; - } + /* --- If an output vector of factors is wanted, produce one --- */ - /* --- Do the Rabin testing --- */ - - rabin_create(&rb, p); - g = MP_NEW; - do { - g = mprand_range(g, p, ev.r, 1); - rc = rabin_test(&rb, g); - if (rc == PGEN_PASS) { - ev.tests--; - if (!ev.tests) - rc = PGEN_DONE; - } - if (oev &&oev(rc, &ev, oec) == PGEN_ABORT) - rc = PGEN_ABORT; - } while (rc == PGEN_PASS); - - rabin_destroy(&rb); - mp_drop(g); - if (rc == PGEN_DONE) - d = p; - else - mp_drop(p); - if (rc == PGEN_ABORT) - goto fail; - if (rc == PGEN_DONE) - goto done; - ev.tests = ntest; - ev.m = 0; - } - } while (comb_next(c, mm, nn)); + if (!(l->f & LIMLEE_KEEPFACTORS)) + v = 0; + else { + if (l->qq.p) + l->nf++; + v = xmalloc(l->nf * sizeof(limlee_factor)); + } - /* --- That failed --- */ + 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 (ev.steps) { - ev.steps--; - if (!ev.steps) { - if (oev) - oev(PGEN_ABORT, &ev, &oec); - goto fail; - } + if (l->qq.p) { + if (v) + v[j++] = l->qq; + else + l->pops->pfree(&l->qq, l); } - for (i = 0; i < mm; i++) - mp_drop(v[i]); - goto again; + xfree(l->v); + l->v = v; - /* --- We did it! --- */ + /* --- Free other resources --- */ -done: { - mp **vv = 0; - if (f) { - if (qq) - nn++; - *nf = nn; - *f = vv = xmalloc(nn * sizeof(mp *)); - } + xfree(l->c); + dstr_destroy(&l->d); - for (i = 0; i < mm; i++) { - if (c[i] && vv) - *vv++ = v[i]; - else if (v[i]) - mp_drop(v[i]); - } - if (qq) { - if (vv) - *vv++ = qq; - else - mp_drop(qq); - } - xfree(v); - xfree(c); - dstr_destroy(&dn); - return (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) +{ + 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; + l.r = r; + + d = pgen(name, d, 0, oev, oec, on, limlee_step, &l, + rabin_iters(pl), pgen_test, &rr); + + if (d && 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; } - /* --- We blew it --- */ - -fail: - for (i = 0; i < mm; i++) - mp_drop(v[i]); - if (qq) - mp_drop(qq); - xfree(v); - xfree(c); - dstr_destroy(&dn); - return (0); + return (d); } /*----- That's all, folks -------------------------------------------------*/