3 * $Id: limlee.c,v 1.6 2001/01/25 21:16:20 mdw Exp $
5 * Generate Lim-Lee primes
7 * (c) 2000 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
14 * Catacomb is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU Library General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
19 * Catacomb is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU Library General Public License for more details.
24 * You should have received a copy of the GNU Library General Public
25 * License along with Catacomb; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
30 /*----- Revision history --------------------------------------------------*
33 * Revision 1.6 2001/01/25 21:16:20 mdw
34 * Boring cosmetic stuff.
36 * Revision 1.5 2000/08/18 19:16:51 mdw
37 * New stepper interface for constructing Lim-Lee primes.
39 * Revision 1.4 2000/08/15 21:45:05 mdw
40 * Use the new trial division equipment in pfilt. This gives a 10%
41 * performance improvement in dsa-gen.t.
43 * Revision 1.3 2000/07/29 09:58:32 mdw
44 * (limlee): Bug fix. Old versions didn't set the filter step if @ql@ was
45 * an exact divisor of @pl@.
47 * Revision 1.2 2000/07/26 18:00:00 mdw
50 * Revision 1.1 2000/07/09 21:30:58 mdw
51 * Lim-Lee prime generation.
55 /*----- Header files ------------------------------------------------------*/
57 #include <mLib/alloc.h>
58 #include <mLib/dstr.h>
66 /*----- Stepping through combinations -------------------------------------*/
68 /* --- @comb_init@ --- *
70 * Arguments: @octet *c@ = pointer to byte-flag array
71 * @unsigned n@ = number of items in the array
72 * @unsigned r@ = number of desired items
76 * Use: Initializes a byte-flag array which, under the control of
77 * @comb_next@, will step through all combinations of @r@ chosen
81 static void comb_init(octet
*c
, unsigned n
, unsigned r
)
84 memset(c
+ (n
- r
), 1, r
);
87 /* --- @comb_next@ --- *
89 * Arguments: @octet *c@ = pointer to byte-flag array
90 * @unsigned n@ = number of items in the array
91 * @unsigned r@ = number of desired items
93 * Returns: Nonzero if another combination was returned, zero if we've
96 * Use: Steps on to the next combination in sequence.
99 static int comb_next(octet
*c
, unsigned n
, unsigned r
)
103 /* --- How the algorithm works --- *
105 * Set bits start at the end and work their way towards the start.
106 * Excepting bits already at the start, we scan for the lowest set bit, and
107 * move it one place nearer the start. A group of bits at the start are
108 * counted and reset just below the `moved' bit. If there is no moved bit
112 /* --- Count the group at the start --- */
121 /* --- Move the next bit down one --- *
123 * There must be one, because otherwise we'd have counted %$r$% bits
136 /*----- Default prime generator -------------------------------------------*/
138 static void llgen(limlee_factor
*f
, unsigned pl
, limlee_stepctx
*l
)
145 p
= mprand(l
->newp
, pl
, l
->r
, 1);
147 p
= pgen(l
->d
.buf
, p
, p
, l
->iev
, l
->iec
, 0, pgen_filter
, &pf
,
148 rabin_iters(pl
), pgen_test
, &r
);
154 static void llfree(limlee_factor
*f
, limlee_stepctx
*l
)
160 static const limlee_primeops primeops_simple
= { llgen
, llfree
};
162 /*----- Lim-Lee stepper ---------------------------------------------------*/
166 * Arguments: @pgen_event *ev@ = pointer to event block
167 * @limlee_stepctx *l@ = pointer to Lim-Lee context
169 * Returns: A @PGEN@ result code.
171 * Use: Initializes the stepper.
174 static int init(pgen_event
*ev
, limlee_stepctx
*l
)
179 /* --- First of all, decide on a number of factors to make --- */
181 l
->nf
= l
->pl
/ l
->ql
;
185 else if (qql
&& l
->nf
> 1) {
190 /* --- Now decide on how many primes I'll actually generate --- *
192 * The formula %$m = \max(3 n + 5, 25)$% comes from GPG's prime generation
196 l
->poolsz
= l
->nf
* 3 + 5;
200 /* --- Allocate and initialize the various tables --- */
202 l
->c
= xmalloc(l
->poolsz
);
203 l
->v
= xmalloc(l
->poolsz
* sizeof(limlee_factor
));
204 comb_init(l
->c
, l
->poolsz
, l
->nf
);
205 for (i
= 0; i
< l
->poolsz
; i
++)
208 /* --- Other bits of initialization --- */
214 l
->pops
= &primeops_simple
;
218 /* --- Find a big prime --- */
223 dstr_putf(&l
->d
, "%s*", ev
->name
);
224 l
->pops
->pgen(&l
->qq
, qql
, l
);
232 * Arguments: @int rq@ = request which triggered this call
233 * @pgen_event *ev@ = pointer to event block
234 * @limlee_stepctx *l@ = pointer to Lim-Lee context
236 * Returns: A @PGEN@ result code.
238 * Use: Initializes the stepper.
241 static int next(int rq
, pgen_event
*ev
, limlee_stepctx
*l
)
252 mpmul mm
= MPMUL_INIT
;
254 /* --- Step on to next combination --- */
256 if (rq
== PGEN_TRY
&& !comb_next(l
->c
, l
->poolsz
, l
->nf
)) {
257 for (i
= 0; i
< l
->poolsz
; i
++) {
258 l
->pops
->pfree(&l
->v
[i
], l
);
262 rq
= PGEN_TRY
; /* For next time through */
264 /* --- Gather up some factors --- */
267 mpmul_add(&mm
, l
->qq
.p
);
268 for (i
= 0; i
< l
->poolsz
; i
++) {
273 dstr_putf(&l
->d
, "%s_%lu", ev
->name
, l
->seq
++);
274 l
->pops
->pgen(&l
->v
[i
], l
->ql
, l
);
276 mpmul_add(&mm
, l
->v
[i
].p
);
279 /* --- Check it for small factors --- */
284 if ((rc
= pfilt_smallfactor(p
)) != PGEN_FAIL
)
295 * Arguments: @pgen_event *ev@ = pointer to event block
296 * @limlee_stepctx *l@ = pointer to Lim-Lee context
298 * Returns: A @PGEN@ result code.
300 * Use: Finalizes the stepper. The output values in the context
301 * take on their final results; other resources are discarded.
304 static int done(pgen_event
*ev
, limlee_stepctx
*l
)
309 /* --- If an output vector of factors is wanted, produce one --- */
311 if (!(l
->f
& LIMLEE_KEEPFACTORS
))
316 v
= xmalloc(l
->nf
* sizeof(limlee_factor
));
319 for (i
= 0, j
= 0; i
< l
->poolsz
; i
++) {
323 l
->pops
->pfree(&l
->v
[i
], l
);
330 l
->pops
->pfree(&l
->qq
, l
);
336 /* --- Free other resources --- */
346 /* --- @limlee_step@ --- */
348 int limlee_step(int rq
, pgen_event
*ev
, void *p
)
350 limlee_stepctx
*l
= p
;
355 if ((rc
= init(ev
, l
)) != PGEN_TRY
)
358 return (next(rq
, ev
, l
));
360 return (done(ev
, l
));
365 /*----- Main code ---------------------------------------------------------*/
367 /* --- @limlee@ --- *
369 * Arguments: @const char *name@ = pointer to name root
370 * @mp *d@ = pointer to destination integer
371 * @mp *newp@ = how to generate factor primes
372 * @unsigned ql@ = size of individual factors
373 * @unsigned pl@ = size of large prime
374 * @grand *r@ = a random number source
375 * @unsigned on@ = number of outer attempts to make
376 * @pgen_proc *oev@ = outer event handler function
377 * @void *oec@ = argument for the outer event handler
378 * @pgen_proc *iev@ = inner event handler function
379 * @void *iec@ = argument for the inner event handler
380 * @size_t *nf@, @mp ***f@ = output array for factors
382 * Returns: A Lim-Lee prime, or null if generation failed.
384 * Use: Generates Lim-Lee primes. A Lim-Lee prime %$p$% is one which
385 * satisfies %$p = 2 \prod_i q_i + 1$%, where all of the %$q_i$%
386 * are large enough to resist square-root discrete log
389 * If we succeed, and @f@ is non-null, we write the array of
390 * factors chosen to @f@ for the benefit of the caller.
393 mp
*limlee(const char *name
, mp
*d
, mp
*newp
,
394 unsigned ql
, unsigned pl
, grand
*r
,
395 unsigned on
, pgen_proc
*oev
, void *oec
,
396 pgen_proc
*iev
, void *iec
,
408 unsigned long seq
= 0;
414 /* --- First of all, decide on a number of factors to make --- */
420 else if (qql
&& nn
> 1) {
425 /* --- Now decide on how many primes I'll actually generate --- *
427 * The formula %$m = \max(3 n + 5, 25)$% comes from GPG's prime generation
435 /* --- Now allocate the working memory --- */
437 v
= xmalloc(mm
* sizeof(mp
*));
440 /* --- Initialize everything and try to find a prime --- */
445 ev
.tests
= ntest
= rabin_iters(pl
);
448 if (oev
&& oev(PGEN_BEGIN
, &ev
, oec
) == PGEN_ABORT
)
453 dstr_putf(&dn
, "%s*", name
);
454 qq
= mprand(d
, qql
, r
, 1);
455 qq
= pgen(dn
.buf
, qq
, qq
, iev
, iec
,
456 0, pgen_filter
, &pf
, rabin_iters(qql
), pgen_test
, &rb
);
460 comb_init(c
, mm
, nn
);
461 for (i
= 0; i
< mm
; i
++)
464 /* --- The main combinations loop --- */
467 mpmul mmul
= MPMUL_INIT
;
469 /* --- Multiply a bunch of primes together --- */
472 mpmul_add(&mmul
, qq
);
473 for (i
= 0; i
< mm
; i
++) {
480 dstr_putf(&dn
, "%s_%lu] = ", name
, seq
++);
481 z
= mprand(newp
, ql
, ev
.r
, 1);
482 z
= pgen(dn
.buf
, z
, z
, iev
, iec
,
483 0, pgen_filter
, &pf
, rabin_iters(ql
), pgen_test
, &rb
);
486 mpmul_add(&mmul
, v
[i
]);
489 /* --- Now do some testing --- */
492 mp
*p
= mpmul_done(&mmul
);
496 /* --- Check for small factors --- */
499 p
= mp_add(p
, p
, MP_ONE
);
500 rc
= pfilt_smallfactor(p
);
501 if (rc
== PGEN_FAIL
) {
506 /* --- Send an event out --- */
509 if (oev
&& oev(PGEN_TRY
, &ev
, oec
) == PGEN_ABORT
) {
514 /* --- Do the Rabin testing --- */
516 rabin_create(&rb
, p
);
519 g
= mprand_range(g
, p
, ev
.r
, 1);
520 rc
= rabin_test(&rb
, g
);
521 if (rc
== PGEN_PASS
) {
526 if (oev
&& oev(rc
, &ev
, oec
) == PGEN_ABORT
)
528 } while (rc
== PGEN_PASS
);
536 if (rc
== PGEN_ABORT
)
543 } while (comb_next(c
, mm
, nn
));
545 /* --- That failed --- */
551 oev(PGEN_ABORT
, &ev
, &oec
);
556 for (i
= 0; i
< mm
; i
++)
560 /* --- We did it! --- */
568 *f
= vv
= xmalloc(nn
* sizeof(mp
*));
571 for (i
= 0; i
< mm
; i
++) {
589 /* --- We blew it --- */
592 for (i
= 0; i
< mm
; i
++)
604 l
.f
= 0; if (f
) l
.f
|= LIMLEE_KEEPFACTORS
;
606 l
.pl
= pl
; l
.ql
= ql
;
611 d
= pgen(name
, d
, 0, oev
, oec
, on
, limlee_step
, &l
,
612 rabin_iters(pl
), pgen_test
, &rr
);
617 v
= xmalloc(l
.nf
* sizeof(mp
*));
618 for (i
= 0; i
< l
.nf
; i
++)
629 /*----- That's all, folks -------------------------------------------------*/