3 * $Id: limlee.h,v 1.4 2001/02/03 11:59:07 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 2001/02/03 11:59:07 mdw
34 * Don't use the @pgen@ random number generator for generating primes: it's
35 * only for testing them. Use a caller-supplied one instead.
37 * Revision 1.3 2000/12/06 20:33:27 mdw
38 * Make flags be macros rather than enumerations, to ensure that they're
41 * Revision 1.2 2000/08/18 19:16:51 mdw
42 * New stepper interface for constructing Lim-Lee primes.
44 * Revision 1.1 2000/07/09 21:30:58 mdw
45 * Lim-Lee prime generation.
49 #ifndef CATACOMB_LIMLEE_H
50 #define CATACOMB_LIMLEE_H
56 /*----- Header files ------------------------------------------------------*/
58 #ifndef CATACOMB_GRAND_H
66 #ifndef CATACOMB_PGEN_H
70 /*----- Data structures ---------------------------------------------------*/
72 typedef struct limlee_factor
{
73 mp
*p
; /* The actual prime */
74 unsigned tag
; /* A tag, usable by the generator */
75 void *more
; /* Pointer to more data */
78 typedef struct limlee_stepctx
{
80 /* --- To be initialized by the caller --- */
82 unsigned f
; /* Various useful flags */
83 mp
*newp
; /* Initial valid for new primes */
84 unsigned ql
, pl
; /* Size of factors and result */
85 const struct limlee_primeops
*pops
; /* Pointer to generator ops */
86 void *pc
; /* Context ptr for generator ops */
87 pgen_proc
*iev
; /* Event handler for inner @pgen@ */
88 void *iec
; /* Context for inner @pgen@ */
89 grand
*r
; /* Random number generator */
91 /* --- Output values --- */
93 size_t nf
; /* Number of factors wanted */
94 limlee_factor
*v
; /* Vector of factors */
96 /* --- Maintained internally --- */
98 octet
*c
; /* Combination byte-flag vector */
99 unsigned long seq
; /* Sequence number for primes */
100 size_t poolsz
; /* Size of the small-prime pool */
101 dstr d
; /* String for subprime name */
102 limlee_factor qq
; /* Big prime to pick up slack */
106 typedef struct limlee_primeops
{
107 void (*pgen
)(limlee_factor */
*f*/
, unsigned /*pl*/, limlee_stepctx */
*l*/
);
108 void (*pfree
)(limlee_factor */
*f*/
, limlee_stepctx */
*l*/
);
113 #define LIMLEE_KEEPFACTORS 1u
115 /*----- The Lim-Lee stepper function --------------------------------------*/
117 extern int limlee_step(int /*rq*/, pgen_event */
*ev*/
, void */
*p*/
);
119 /*----- Functions provided ------------------------------------------------*/
121 /* --- @limlee@ --- *
123 * Arguments: @const char *name@ = pointer to name root
124 * @mp *d@ = pointer to destination integer
125 * @mp *newp@ = how to generate factor primes
126 * @unsigned ql@ = size of individual factors
127 * @unsigned pl@ = size of large prime
128 * @grand *r@ = a random number source
129 * @unsigned on@ = number of outer attempts to make
130 * @pgen_proc *oev@ = outer event handler function
131 * @void *oec@ = argument for the outer event handler
132 * @pgen_proc *iev@ = inner event handler function
133 * @void *iec@ = argument for the inner event handler
134 * @size_t *nf@, @mp ***f@ = output array for factors
136 * Returns: A Lim-Lee prime, or null if generation failed.
138 * Use: Generates Lim-Lee primes. A Lim-Lee prime %$p$% is one which
139 * satisfies %$p = 2 \prod_i q_i + 1$%, where all of the %$q_i$%
140 * are large enough to resist square-root discrete log
143 * If we succeed, and @f@ is non-null, we write the array of
144 * factors chosen to @f@ for the benefit of the caller.
147 extern mp
*limlee(const char */
*name*/
, mp */
*d*/
, mp */
*newp*/
,
148 unsigned /*ql*/, unsigned /*pl*/, grand */
*r*/
,
149 unsigned /*on*/, pgen_proc */
*oev*/
, void */
*oec*/
,
150 pgen_proc */
*iev*/
, void */
*iec*/
,
151 size_t */
*nf*/
, mp
***/
*f*/
);
153 /*----- That's all, folks -------------------------------------------------*/