3 * Generate Lim-Lee primes
5 * (c) 2000 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
28 /*----- Header files ------------------------------------------------------*/
30 #include <mLib/alloc.h>
31 #include <mLib/dstr.h>
39 /*----- Stepping through combinations -------------------------------------*/
41 /* --- @comb_init@ --- *
43 * Arguments: @octet *c@ = pointer to byte-flag array
44 * @unsigned n@ = number of items in the array
45 * @unsigned r@ = number of desired items
49 * Use: Initializes a byte-flag array which, under the control of
50 * @comb_next@, will step through all combinations of @r@ chosen
54 static void comb_init(octet *c, unsigned n, unsigned r)
57 memset(c + (n - r), 1, r);
60 /* --- @comb_next@ --- *
62 * Arguments: @octet *c@ = pointer to byte-flag array
63 * @unsigned n@ = number of items in the array
64 * @unsigned r@ = number of desired items
66 * Returns: Nonzero if another combination was returned, zero if we've
69 * Use: Steps on to the next combination in sequence.
72 static int comb_next(octet *c, unsigned n, unsigned r)
76 /* --- How the algorithm works --- *
78 * Set bits start at the end and work their way towards the start.
79 * Excepting bits already at the start, we scan for the lowest set bit, and
80 * move it one place nearer the start. A group of bits at the start are
81 * counted and reset just below the `moved' bit. If there is no moved bit
85 /* --- Count the group at the start --- */
94 /* --- Move the next bit down one --- *
96 * There must be one, because otherwise we'd have counted %$r$% bits
109 /*----- Default prime generator -------------------------------------------*/
111 static void llgen(limlee_factor *f, unsigned pl, limlee_stepctx *l)
117 p = mprand(l->newp, pl, l->r, 1);
119 p = pgen(l->u.s.name, p, p, l->iev, l->iec, 0, pgen_filter, &pf,
120 rabin_iters(pl), pgen_test, &r);
124 static void llfree(limlee_factor *f, limlee_stepctx *l)
129 static const limlee_primeops primeops_simple = { llgen, llfree };
131 /*----- Lim-Lee stepper ---------------------------------------------------*/
135 * Arguments: @pgen_event *ev@ = pointer to event block
136 * @limlee_stepctx *l@ = pointer to Lim-Lee context
138 * Returns: A @PGEN@ result code.
140 * Use: Initializes the stepper.
143 static int init(pgen_event *ev, limlee_stepctx *l)
147 /* --- First of all, decide on a number of factors to make --- */
149 l->nf = l->pl / l->ql;
150 if (l->nf < 2) return (PGEN_ABORT);
153 /* --- Now decide on how many primes I'll actually generate --- *
155 * The formula %$m = \max(3 n + 5, 25)$% comes from GPG's prime generation
159 l->poolsz = l->nf * 3 + 5;
163 /* --- Allocate and initialize the various tables --- */
165 l->c = xmalloc(l->poolsz);
166 l->v = xmalloc(l->poolsz * sizeof(limlee_factor));
167 comb_init(l->c, l->poolsz, l->nf);
168 for (i = 0; i < l->poolsz; i++)
171 /* --- Other bits of initialization --- */
175 l->pops = &primeops_simple;
179 /* --- Find a big prime later --- */
188 * Arguments: @int rq@ = request which triggered this call
189 * @pgen_event *ev@ = pointer to event block
190 * @limlee_stepctx *l@ = pointer to Lim-Lee context
192 * Returns: A @PGEN@ result code.
194 * Use: Initializes the stepper.
197 static int next(int rq, pgen_event *ev, limlee_stepctx *l)
209 mpmul mm = MPMUL_INIT;
211 /* --- Step on to next combination --- */
213 if (rq == PGEN_TRY && !comb_next(l->c, l->poolsz, l->nf)) {
214 for (i = 0; i < l->poolsz; i++) {
215 l->pops->pfree(&l->v[i], l);
219 rq = PGEN_TRY; /* For next time through */
221 /* --- If the large factor is performing badly, make a new one --- */
224 dist = l->u.s.disp < 0 ? -l->u.s.disp : l->u.s.disp;
225 if (dist && dist > l->u.s.steps/3) {
226 l->pops->pfree(&l->qq, l);
231 /* --- Gather up some factors --- */
233 if (l->qq.p) mpmul_add(&mm, l->qq.p);
234 for (i = 0; i < l->poolsz; i++) {
239 dstr_putf(&d, "%s_%lu", ev->name, l->seq++);
241 l->pops->pgen(&l->v[i], l->ql, l);
243 { mp_drop(mpmul_done(&mm)); rc = PGEN_ABORT; goto end; }
245 mpmul_add(&mm, l->v[i].p);
248 /* --- Check on the large factor --- */
253 dstr_putf(&d, "%s*_%lu", ev->name, l->seq++);
255 l->pops->pgen(&l->qq, l->pl - mp_bits(p), l);
256 if (!l->qq.p) { MP_DROP(p); p = 0; rc = PGEN_ABORT; break; }
257 l->u.s.steps = l->u.s.disp = 0;
258 p = mp_mul(p, p, l->qq.p);
268 } else if (nb > l->pl) {
273 /* --- Check it for small factors --- */
275 if ((rc = pfilt_smallfactor(p)) != PGEN_FAIL)
288 * Arguments: @pgen_event *ev@ = pointer to event block
289 * @limlee_stepctx *l@ = pointer to Lim-Lee context
291 * Returns: A @PGEN@ result code.
293 * Use: Finalizes the stepper. The output values in the context
294 * take on their final results; other resources are discarded.
297 static int done(pgen_event *ev, limlee_stepctx *l)
302 /* --- If an output vector of factors is wanted, produce one --- */
304 if (!(l->f & LIMLEE_KEEPFACTORS))
309 v = xmalloc(l->nf * sizeof(limlee_factor));
312 for (i = 0, j = 0; i < l->poolsz; i++) {
316 l->pops->pfree(&l->v[i], l);
323 l->pops->pfree(&l->qq, l);
329 /* --- Free other resources --- */
338 /* --- @limlee_step@ --- */
340 int limlee_step(int rq, pgen_event *ev, void *p)
342 limlee_stepctx *l = p;
347 if ((rc = init(ev, l)) != PGEN_TRY)
350 return (next(rq, ev, l));
352 return (done(ev, l));
357 /*----- Main code ---------------------------------------------------------*/
359 /* --- @limlee@ --- *
361 * Arguments: @const char *name@ = pointer to name root
362 * @mp *d@ = pointer to destination integer
363 * @mp *newp@ = how to generate factor primes
364 * @unsigned ql@ = size of individual factors
365 * @unsigned pl@ = size of large prime
366 * @grand *r@ = a random number source
367 * @unsigned on@ = number of outer attempts to make
368 * @pgen_proc *oev@ = outer event handler function
369 * @void *oec@ = argument for the outer event handler
370 * @pgen_proc *iev@ = inner event handler function
371 * @void *iec@ = argument for the inner event handler
372 * @size_t *nf@, @mp ***f@ = output array for factors
374 * Returns: A Lim-Lee prime, or null if generation failed.
376 * Use: Generates Lim-Lee primes. A Lim-Lee prime %$p$% is one which
377 * satisfies %$p = 2 \prod_i q_i + 1$%, where all of the %$q_i$%
378 * are large enough to resist square-root discrete log
381 * If we succeed, and @f@ is non-null, we write the array of
382 * factors chosen to @f@ for the benefit of the caller.
385 mp *limlee(const char *name, mp *d, mp *newp,
386 unsigned ql, unsigned pl, grand *r,
387 unsigned on, pgen_proc *oev, void *oec,
388 pgen_proc *iev, void *iec,
396 l.f = 0; if (f) l.f |= LIMLEE_KEEPFACTORS;
398 l.pl = pl; l.ql = ql;
404 d = pgen(name, d, 0, oev, oec, on, limlee_step, &l,
405 rabin_iters(pl), pgen_test, &rr);
409 for (i = 0; i < l.nf; i++)
410 if (l.v[i].p) llfree(&l.v[i], &l);
412 v = xmalloc(l.nf * sizeof(mp *));
413 for (i = 0; i < l.nf; i++)
424 /*----- That's all, folks -------------------------------------------------*/