chiark / gitweb /
math/f25519.[ch]: More field operations.
[catacomb] / math / limlee.h
CommitLineData
04361334 1/* -*-c-*-
04361334 2 *
3 * Generate Lim-Lee primes
4 *
5 * (c) 2000 Straylight/Edgeware
6 */
7
45c0fd36 8/*----- Licensing notice --------------------------------------------------*
04361334 9 *
10 * This file is part of Catacomb.
11 *
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.
45c0fd36 16 *
04361334 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.
45c0fd36 21 *
04361334 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,
25 * MA 02111-1307, USA.
26 */
27
04361334 28#ifndef CATACOMB_LIMLEE_H
29#define CATACOMB_LIMLEE_H
30
31#ifdef __cplusplus
32 extern "C" {
33#endif
34
35/*----- Header files ------------------------------------------------------*/
36
37#ifndef CATACOMB_GRAND_H
38# include "grand.h"
39#endif
40
41#ifndef CATACOMB_MP_H
42# include "mp.h"
43#endif
44
45#ifndef CATACOMB_PGEN_H
46# include "pgen.h"
47#endif
48
10217a5c 49/*----- Data structures ---------------------------------------------------*/
50
51typedef struct limlee_factor {
52 mp *p; /* The actual prime */
53 unsigned tag; /* A tag, usable by the generator */
54 void *more; /* Pointer to more data */
55} limlee_factor;
56
57typedef struct limlee_stepctx {
58
59 /* --- To be initialized by the caller --- */
60
61 unsigned f; /* Various useful flags */
62 mp *newp; /* Initial valid for new primes */
63 unsigned ql, pl; /* Size of factors and result */
64 const struct limlee_primeops *pops; /* Pointer to generator ops */
65 void *pc; /* Context ptr for generator ops */
66 pgen_proc *iev; /* Event handler for inner @pgen@ */
67 void *iec; /* Context for inner @pgen@ */
383e235b 68 grand *r; /* Random number generator */
10217a5c 69
70 /* --- Output values --- */
71
72 size_t nf; /* Number of factors wanted */
73 limlee_factor *v; /* Vector of factors */
74
75 /* --- Maintained internally --- */
76
77 octet *c; /* Combination byte-flag vector */
10217a5c 78 unsigned long seq; /* Sequence number for primes */
79 size_t poolsz; /* Size of the small-prime pool */
0b09aab8
MW
80 union {
81 dstr d; /* Obsolete; for ABI compat */
82 struct {
83 char *name; /* Name, for @primeops@ */
84 int steps, disp; /* Track how good @qq@ is */
85 } s;
86 } u;
10217a5c 87 limlee_factor qq; /* Big prime to pick up slack */
88
89} limlee_stepctx;
90
91typedef struct limlee_primeops {
92 void (*pgen)(limlee_factor */*f*/, unsigned /*pl*/, limlee_stepctx */*l*/);
93 void (*pfree)(limlee_factor */*f*/, limlee_stepctx */*l*/);
94} limlee_primeops;
95
96/* --- Flags --- */
97
16efd15b 98#define LIMLEE_KEEPFACTORS 1u
10217a5c 99
100/*----- The Lim-Lee stepper function --------------------------------------*/
101
ab6ce636 102extern pgen_proc limlee_step;
10217a5c 103
04361334 104/*----- Functions provided ------------------------------------------------*/
105
106/* --- @limlee@ --- *
107 *
108 * Arguments: @const char *name@ = pointer to name root
109 * @mp *d@ = pointer to destination integer
110 * @mp *newp@ = how to generate factor primes
111 * @unsigned ql@ = size of individual factors
112 * @unsigned pl@ = size of large prime
113 * @grand *r@ = a random number source
114 * @unsigned on@ = number of outer attempts to make
115 * @pgen_proc *oev@ = outer event handler function
116 * @void *oec@ = argument for the outer event handler
117 * @pgen_proc *iev@ = inner event handler function
118 * @void *iec@ = argument for the inner event handler
119 * @size_t *nf@, @mp ***f@ = output array for factors
120 *
121 * Returns: A Lim-Lee prime, or null if generation failed.
122 *
123 * Use: Generates Lim-Lee primes. A Lim-Lee prime %$p$% is one which
124 * satisfies %$p = 2 \prod_i q_i + 1$%, where all of the %$q_i$%
125 * are large enough to resist square-root discrete log
126 * algorithms.
127 *
128 * If we succeed, and @f@ is non-null, we write the array of
129 * factors chosen to @f@ for the benefit of the caller.
130 */
131
132extern 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*/,
136 size_t */*nf*/, mp ***/*f*/);
137
138/*----- That's all, folks -------------------------------------------------*/
139
140#ifdef __cplusplus
141 }
142#endif
143
144#endif