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