45f579d1fc5f6c431a1be3ee456f1f9cd6e7fa0f
3 * $Id: limlee.c,v 1.4 2000/08/15 21:45:05 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.4 2000/08/15 21:45:05 mdw
34 * Use the new trial division equipment in pfilt. This gives a 10%
35 * performance improvement in dsa-gen.t.
37 * Revision 1.3 2000/07/29 09:58:32 mdw
38 * (limlee): Bug fix. Old versions didn't set the filter step if @ql@ was
39 * an exact divisor of @pl@.
41 * Revision 1.2 2000/07/26 18:00:00 mdw
44 * Revision 1.1 2000/07/09 21:30:58 mdw
45 * Lim-Lee prime generation.
49 /*----- Header files ------------------------------------------------------*/
51 #include <mLib/alloc.h>
52 #include <mLib/dstr.h>
58 #include "primorial.h"
61 /*----- Main code ---------------------------------------------------------*/
65 * Arguments: @const char *name@ = pointer to name root
66 * @mp *d@ = pointer to destination integer
67 * @mp *newp@ = how to generate factor primes
68 * @unsigned ql@ = size of individual factors
69 * @unsigned pl@ = size of large prime
70 * @grand *r@ = a random number source
71 * @unsigned on@ = number of outer attempts to make
72 * @pgen_proc *oev@ = outer event handler function
73 * @void *oec@ = argument for the outer event handler
74 * @pgen_proc *iev@ = inner event handler function
75 * @void *iec@ = argument for the inner event handler
76 * @size_t *nf@, @mp ***f@ = output array for factors
78 * Returns: A Lim-Lee prime, or null if generation failed.
80 * Use: Generates Lim-Lee primes. A Lim-Lee prime %$p$% is one which
81 * satisfies %$p = 2 \prod_i q_i + 1$%, where all of the %$q_i$%
82 * are large enough to resist square-root discrete log
85 * If we succeed, and @f@ is non-null, we write the array of
86 * factors chosen to @f@ for the benefit of the caller.
89 static void comb_init(octet
*c
, unsigned n
, unsigned r
)
92 memset(c
+ (n
- r
), 1, r
);
95 static int comb_next(octet
*c
, unsigned n
, unsigned r
)
99 /* --- How the algorithm works --- *
101 * Set bits start at the end and work their way towards the start.
102 * Excepting bits already at the start, we scan for the lowest set bit, and
103 * move it one place nearer the start. A group of bits at the start are
104 * counted and reset just below the `moved' bit. If there is no moved bit
108 /* --- Count the group at the start --- */
117 /* --- Move the next bit down one --- *
119 * There must be one, because otherwise we'd have counted %$r$% bits
132 mp
*limlee(const char *name
, mp
*d
, mp
*newp
,
133 unsigned ql
, unsigned pl
, grand
*r
,
134 unsigned on
, pgen_proc
*oev
, void *oec
,
135 pgen_proc
*iev
, void *iec
,
146 unsigned long seq
= 0;
152 /* --- First of all, decide on a number of factors to make --- */
158 else if (qql
&& nn
> 1) {
163 /* --- Now decide on how many primes I'll actually generate --- *
165 * The formula %$m = \max(3 n + 5, 25)$% comes from GPG's prime generation
173 /* --- Now allocate the working memory --- */
175 v
= xmalloc(mm
* sizeof(mp
*));
178 /* --- Initialize everything and try to find a prime --- */
183 ev
.tests
= ntest
= rabin_iters(pl
);
186 if (oev
&& oev(PGEN_BEGIN
, &ev
, oec
) == PGEN_ABORT
)
191 dstr_putf(&dn
, "%s [+]", name
);
192 qq
= mprand(d
, qql
, r
, 1);
193 qq
= pgen(dn
.buf
, qq
, qq
, iev
, iec
,
194 0, pgen_filter
, &pf
, rabin_iters(qql
), pgen_test
, &rb
);
198 comb_init(c
, mm
, nn
);
199 for (i
= 0; i
< mm
; i
++)
202 /* --- The main combinations loop --- */
205 mpmul mmul
= MPMUL_INIT
;
207 /* --- Multiply a bunch of primes together --- */
210 mpmul_add(&mmul
, qq
);
212 for (i
= 0; i
< mm
; i
++) {
219 dstr_putf(&dn
, "%s [%lu] = ", name
, seq
++);
220 z
= mprand(newp
, ql
, ev
.r
, 1);
221 z
= pgen(dn
.buf
, z
, z
, iev
, iec
,
222 0, pgen_filter
, &pf
, rabin_iters(ql
), pgen_test
, &rb
);
225 mpmul_add(&mmul
, v
[i
]);
228 /* --- Now do some testing --- */
231 mp
*p
= mpmul_done(&mmul
);
235 /* --- Check for small factors --- */
238 p
= mp_add(p
, p
, MP_ONE
);
239 rc
= pfilt_smallfactor(p
);
240 if (rc
== PGEN_FAIL
) {
245 /* --- Send an event out --- */
248 if (oev
&& oev(PGEN_TRY
, &ev
, oec
) == PGEN_ABORT
) {
253 /* --- Do the Rabin testing --- */
255 rabin_create(&rb
, p
);
258 g
= mprand_range(g
, p
, ev
.r
, 1);
259 rc
= rabin_test(&rb
, g
);
260 if (rc
== PGEN_PASS
) {
265 if (oev
&&oev(rc
, &ev
, oec
) == PGEN_ABORT
)
267 } while (rc
== PGEN_PASS
);
275 if (rc
== PGEN_ABORT
)
282 } while (comb_next(c
, mm
, nn
));
284 /* --- That failed --- */
290 oev(PGEN_ABORT
, &ev
, &oec
);
295 for (i
= 0; i
< mm
; i
++)
299 /* --- We did it! --- */
307 *f
= vv
= xmalloc(nn
* sizeof(mp
*));
310 for (i
= 0; i
< mm
; i
++) {
328 /* --- We blew it --- */
331 for (i
= 0; i
< mm
; i
++)
341 /*----- That's all, folks -------------------------------------------------*/