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
)
118 p
= mprand(l
->newp
, pl
, l
->r
, 1);
120 p
= pgen(l
->u
.s
.name
, p
, p
, l
->iev
, l
->iec
, 0, pgen_filter
, &pf
,
121 rabin_iters(pl
), pgen_test
, &r
);
127 static void llfree(limlee_factor
*f
, limlee_stepctx
*l
)
132 static const limlee_primeops primeops_simple
= { llgen
, llfree
};
134 /*----- Lim-Lee stepper ---------------------------------------------------*/
138 * Arguments: @pgen_event *ev@ = pointer to event block
139 * @limlee_stepctx *l@ = pointer to Lim-Lee context
141 * Returns: A @PGEN@ result code.
143 * Use: Initializes the stepper.
146 static int init(pgen_event
*ev
, limlee_stepctx
*l
)
150 /* --- First of all, decide on a number of factors to make --- */
152 l
->nf
= l
->pl
/ l
->ql
;
153 if (l
->nf
< 2) return (PGEN_ABORT
);
156 /* --- Now decide on how many primes I'll actually generate --- *
158 * The formula %$m = \max(3 n + 5, 25)$% comes from GPG's prime generation
162 l
->poolsz
= l
->nf
* 3 + 5;
166 /* --- Allocate and initialize the various tables --- */
168 l
->c
= xmalloc(l
->poolsz
);
169 l
->v
= xmalloc(l
->poolsz
* sizeof(limlee_factor
));
170 comb_init(l
->c
, l
->poolsz
, l
->nf
);
171 for (i
= 0; i
< l
->poolsz
; i
++)
174 /* --- Other bits of initialization --- */
178 l
->pops
= &primeops_simple
;
182 /* --- Find a big prime later --- */
191 * Arguments: @int rq@ = request which triggered this call
192 * @pgen_event *ev@ = pointer to event block
193 * @limlee_stepctx *l@ = pointer to Lim-Lee context
195 * Returns: A @PGEN@ result code.
197 * Use: Initializes the stepper.
200 static int next(int rq
, pgen_event
*ev
, limlee_stepctx
*l
)
212 mpmul mm
= MPMUL_INIT
;
214 /* --- Step on to next combination --- */
216 if (rq
== PGEN_TRY
&& !comb_next(l
->c
, l
->poolsz
, l
->nf
)) {
217 for (i
= 0; i
< l
->poolsz
; i
++) {
218 l
->pops
->pfree(&l
->v
[i
], l
);
222 rq
= PGEN_TRY
; /* For next time through */
224 /* --- If the large factor is performing badly, make a new one --- */
227 dist
= l
->u
.s
.disp
< 0 ?
-l
->u
.s
.disp
: l
->u
.s
.disp
;
228 if (dist
&& dist
> l
->u
.s
.steps
/dist
) {
229 l
->pops
->pfree(&l
->qq
, l
);
234 /* --- Gather up some factors --- */
236 if (l
->qq
.p
) mpmul_add(&mm
, l
->qq
.p
);
237 for (i
= 0; i
< l
->poolsz
; i
++) {
242 dstr_putf(&d
, "%s_%lu", ev
->name
, l
->seq
++);
244 l
->pops
->pgen(&l
->v
[i
], l
->ql
, l
);
246 mpmul_add(&mm
, l
->v
[i
].p
);
249 /* --- Check on the large factor --- */
254 dstr_putf(&d
, "%s*_%lu", ev
->name
, l
->seq
++);
256 l
->pops
->pgen(&l
->qq
, l
->pl
- mp_bits(p
), l
);
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
)
287 * Arguments: @pgen_event *ev@ = pointer to event block
288 * @limlee_stepctx *l@ = pointer to Lim-Lee context
290 * Returns: A @PGEN@ result code.
292 * Use: Finalizes the stepper. The output values in the context
293 * take on their final results; other resources are discarded.
296 static int done(pgen_event
*ev
, limlee_stepctx
*l
)
301 /* --- If an output vector of factors is wanted, produce one --- */
303 if (!(l
->f
& LIMLEE_KEEPFACTORS
))
308 v
= xmalloc(l
->nf
* sizeof(limlee_factor
));
311 for (i
= 0, j
= 0; i
< l
->poolsz
; i
++) {
315 l
->pops
->pfree(&l
->v
[i
], l
);
322 l
->pops
->pfree(&l
->qq
, l
);
328 /* --- Free other resources --- */
337 /* --- @limlee_step@ --- */
339 int limlee_step(int rq
, pgen_event
*ev
, void *p
)
341 limlee_stepctx
*l
= p
;
346 if ((rc
= init(ev
, l
)) != PGEN_TRY
)
349 return (next(rq
, ev
, l
));
351 return (done(ev
, l
));
356 /*----- Main code ---------------------------------------------------------*/
358 /* --- @limlee@ --- *
360 * Arguments: @const char *name@ = pointer to name root
361 * @mp *d@ = pointer to destination integer
362 * @mp *newp@ = how to generate factor primes
363 * @unsigned ql@ = size of individual factors
364 * @unsigned pl@ = size of large prime
365 * @grand *r@ = a random number source
366 * @unsigned on@ = number of outer attempts to make
367 * @pgen_proc *oev@ = outer event handler function
368 * @void *oec@ = argument for the outer event handler
369 * @pgen_proc *iev@ = inner event handler function
370 * @void *iec@ = argument for the inner event handler
371 * @size_t *nf@, @mp ***f@ = output array for factors
373 * Returns: A Lim-Lee prime, or null if generation failed.
375 * Use: Generates Lim-Lee primes. A Lim-Lee prime %$p$% is one which
376 * satisfies %$p = 2 \prod_i q_i + 1$%, where all of the %$q_i$%
377 * are large enough to resist square-root discrete log
380 * If we succeed, and @f@ is non-null, we write the array of
381 * factors chosen to @f@ for the benefit of the caller.
384 mp
*limlee(const char *name
, mp
*d
, mp
*newp
,
385 unsigned ql
, unsigned pl
, grand
*r
,
386 unsigned on
, pgen_proc
*oev
, void *oec
,
387 pgen_proc
*iev
, void *iec
,
393 l
.f
= 0; if (f
) l
.f
|= LIMLEE_KEEPFACTORS
;
395 l
.pl
= pl
; l
.ql
= ql
;
401 d
= pgen(name
, d
, 0, oev
, oec
, on
, limlee_step
, &l
,
402 rabin_iters(pl
), pgen_test
, &rr
);
407 v
= xmalloc(l
.nf
* sizeof(mp
*));
408 for (i
= 0; i
< l
.nf
; i
++)
418 /*----- That's all, folks -------------------------------------------------*/