/* -*-c-*-
*
- * $Id: limlee.c,v 1.6 2001/01/25 21:16:20 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.
*
* 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.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@.
- *
- * 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 <mLib/alloc.h>
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;
else {
dstr_putf(&l->d, "%s*", ev->name);
l->pops->pgen(&l->qq, qql, l);
- }
+ }
return (PGEN_TRY);
}
mp *p;
int rc;
- if (ev->m)
- mp_drop(ev->m);
- l->r = ev->r;
+ mp_drop(ev->m);
for (;;) {
size_t i;
return (done(ev, l));
}
return (PGEN_ABORT);
-}
+}
/*----- Main code ---------------------------------------------------------*/
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);
- if (f) {
+ if (d && f) {
mp **v;
size_t i;
v = xmalloc(l.nf * sizeof(mp *));
}
return (d);
-#endif
}
/*----- That's all, folks -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff