/* -*-c-*-
*
- * $Id: limlee.c,v 1.5 2000/08/18 19:16:51 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.
*
static void llfree(limlee_factor *f, limlee_stepctx *l)
{
- if (f->p)
- mp_drop(f->p);
+ mp_drop(f->p);
}
static const limlee_primeops primeops_simple = { llgen, llfree };
/* --- Other bits of initialization --- */
l->seq = 0;
- l->r = ev->r;
dstr_create(&l->d);
if (!l->pops) {
l->pops = &primeops_simple;
mp *p;
int rc;
- if (ev->m)
- mp_drop(ev->m);
- l->r = ev->r;
+ mp_drop(ev->m);
for (;;) {
size_t i;
pgen_proc *iev, void *iec,
size_t *nf, mp ***f)
{
-#ifdef notdef
- 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;
-
- /* --- 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;
- }
-
- /* --- 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.
- */
-
- mm = nn * 3 + 5;
- if (mm < 25)
- mm = 25;
-
- /* --- Now allocate the working memory --- */
-
- v = xmalloc(mm * sizeof(mp *));
- c = xmalloc(mm);
-
- /* --- Initialize everything and try to find a prime --- */
-
- ev.name = name;
- ev.m = 0;
- ev.steps = on;
- ev.tests = ntest = rabin_iters(pl);
- ev.r = r;
-
- if (oev && oev(PGEN_BEGIN, &ev, oec) == PGEN_ABORT)
- goto fail;
-
- 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);
- }
-
-again:
- comb_init(c, mm, nn);
- for (i = 0; i < mm; i++)
- v[i] = 0;
-
- /* --- The main combinations loop --- */
-
- do {
- mpmul mmul = MPMUL_INIT;
-
- /* --- Multiply a bunch of primes together --- */
-
- if (qq) {
- mpmul_add(&mmul, qq);
- }
- for (i = 0; i < mm; i++) {
- if (!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;
- }
- mpmul_add(&mmul, v[i]);
- }
-
- /* --- Now do some testing --- */
-
- {
- mp *p = mpmul_done(&mmul);
- mp *g;
- int rc;
-
- /* --- Check for small factors --- */
-
- p = mp_lsl(p, p, 1);
- p = mp_add(p, p, MP_ONE);
- rc = pfilt_smallfactor(p);
- if (rc == PGEN_FAIL) {
- mp_drop(p);
- continue;
- }
-
- /* --- Send an event out --- */
-
- ev.m = p;
- if (oev && oev(PGEN_TRY, &ev, oec) == PGEN_ABORT) {
- mp_drop(p);
- goto fail;
- }
-
- /* --- 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));
-
- /* --- That failed --- */
-
- if (ev.steps) {
- ev.steps--;
- if (!ev.steps) {
- if (oev)
- oev(PGEN_ABORT, &ev, &oec);
- goto fail;
- }
- }
-
- for (i = 0; i < mm; i++)
- mp_drop(v[i]);
- goto again;
-
- /* --- We did it! --- */
-
-done: {
- mp **vv = 0;
- if (f) {
- if (qq)
- nn++;
- *nf = nn;
- *f = vv = xmalloc(nn * sizeof(mp *));
- }
-
- 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);
- }
-
- /* --- 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);
-#else
limlee_stepctx l;
rabin rr;
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);
}
return (d);
-#endif
}
/*----- That's all, folks -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff