X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/10217a5c148f63def6fc564960a9f28ae42d52dc..f7c19c5b761808de4ec198765ea7608293706a91:/limlee.c diff --git a/limlee.c b/limlee.c index 60f6bb5..b6fc4d6 100644 --- a/limlee.c +++ b/limlee.c @@ -1,13 +1,13 @@ /* -*-c-*- * - * $Id: limlee.c,v 1.5 2000/08/18 19:16:51 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,40 +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.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@. - * - * 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 @@ -150,8 +128,7 @@ again: 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 }; @@ -205,7 +182,6 @@ static int init(pgen_event *ev, limlee_stepctx *l) /* --- Other bits of initialization --- */ l->seq = 0; - l->r = ev->r; dstr_create(&l->d); if (!l->pops) { l->pops = &primeops_simple; @@ -219,7 +195,7 @@ static int init(pgen_event *ev, limlee_stepctx *l) else { dstr_putf(&l->d, "%s*", ev->name); l->pops->pgen(&l->qq, qql, l); - } + } return (PGEN_TRY); } @@ -240,9 +216,7 @@ 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; + mp_drop(ev->m); for (;;) { size_t i; @@ -357,7 +331,7 @@ int limlee_step(int rq, pgen_event *ev, void *p) return (done(ev, l)); } return (PGEN_ABORT); -} +} /*----- Main code ---------------------------------------------------------*/ @@ -393,209 +367,6 @@ mp *limlee(const char *name, mp *d, mp *newp, 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; @@ -605,11 +376,12 @@ fail: 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) { + if (d && f) { mp **v; size_t i; v = xmalloc(l.nf * sizeof(mp *)); @@ -621,7 +393,6 @@ fail: } return (d); -#endif } /*----- That's all, folks -------------------------------------------------*/