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