/* -*-c-*-
*
- * $Id: limlee.c,v 1.3 2000/07/29 09:58:32 mdw Exp $
+ * $Id: limlee.c,v 1.8 2001/02/03 11:59:07 mdw Exp $
*
* Generate Lim-Lee primes
*
/*----- Revision history --------------------------------------------------*
*
* $Log: limlee.c,v $
+ * Revision 1.8 2001/02/03 11:59:07 mdw
+ * Don't use the @pgen@ random number generator for generating primes: it's
+ * only for testing them. Use a caller-supplied one instead.
+ *
+ * Revision 1.7 2001/01/25 21:40:44 mdw
+ * Remove dead code now that the new stepper structure is trustworthy.
+ *
+ * Revision 1.6 2001/01/25 21:16:20 mdw
+ * Boring cosmetic stuff.
+ *
+ * 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.
+ *
* 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@.
#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
- *
- * 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)
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);
}
-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 --- *
* 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);
+}
+
+/* --- @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.
+ */
- /* --- The main combinations loop --- */
+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 (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 -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff