Commit | Line | Data |
---|---|---|
a30942cc | 1 | /* -*-c-*- |
a30942cc | 2 | * |
3 | * Generate `strong' prime numbers | |
4 | * | |
5 | * (c) 1999 Straylight/Edgeware | |
6 | */ | |
7 | ||
45c0fd36 | 8 | /*----- Licensing notice --------------------------------------------------* |
a30942cc | 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 | * |
a30942cc | 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 | * |
a30942cc | 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 | ||
a30942cc | 28 | #ifndef CATACOMB_STRONGPRIME_H |
29 | #define CATACOMB_STRONGPRIME_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_PGEN_H | |
42 | # include "pgen.h" | |
43 | #endif | |
44 | ||
45 | /*----- Functions provided ------------------------------------------------*/ | |
46 | ||
052b36d0 | 47 | /* --- @strongprime_setup@ --- * |
48 | * | |
49 | * Arguments: @const char *name@ = pointer to name root | |
50 | * @mp *d@ = destination for search start point | |
51 | * @pfilt *f@ = where to store filter jump context | |
52 | * @unsigned nbits@ = number of bits wanted | |
53 | * @grand *r@ = random number source | |
54 | * @unsigned n@ = number of attempts to make | |
55 | * @pgen_proc *event@ = event handler function | |
56 | * @void *ectx@ = argument for the event handler | |
57 | * | |
58 | * Returns: A starting point for a `strong' prime search, or zero. | |
59 | * | |
60 | * Use: Sets up for a strong prime search, so that primes with | |
61 | * particular properties can be found. It's probably important | |
62 | * to note that the number left in the filter context @f@ is | |
e62e86d3 MW |
63 | * congruent to 2 (mod 4); that the jump value is twice the |
64 | * product of two large primes; and that the starting point is | |
65 | * at least %$3 \cdot 2^{N-2}$%. (Hence, if you multiply two | |
66 | * such numbers, the product is at least | |
67 | * | |
68 | * %$9 \cdot 2^{2N-4} > 2^{2N-1}$% | |
69 | * | |
70 | * i.e., it will be (at least) a %$2 N$%-bit value. | |
052b36d0 | 71 | */ |
72 | ||
73 | extern mp *strongprime_setup(const char */*name*/, mp */*d*/, pfilt */*f*/, | |
74 | unsigned /*nbits*/, grand */*r*/, | |
75 | unsigned /*n*/, pgen_proc */*event*/, | |
76 | void */*ectx*/); | |
77 | ||
a30942cc | 78 | /* --- @strongprime@ --- * |
79 | * | |
80 | * Arguments: @const char *name@ = pointer to name root | |
81 | * @mp *d@ = destination integer | |
82 | * @unsigned nbits@ = number of bits wanted | |
83 | * @grand *r@ = random number source | |
84 | * @unsigned n@ = number of attempts to make | |
85 | * @pgen_proc *event@ = event handler function | |
86 | * @void *ectx@ = argument for the event handler | |
87 | * | |
88 | * Returns: A `strong' prime, or zero. | |
89 | * | |
90 | * Use: Finds `strong' primes. A strong prime %$p$% is such that | |
91 | * | |
92 | * * %$p - 1$% has a large prime factor %$r$%, | |
93 | * * %$p + 1$% has a large prime factor %$s$%, and | |
94 | * * %$r - 1$% has a large prime factor %$t$%. | |
a30942cc | 95 | */ |
96 | ||
97 | extern mp *strongprime(const char */*name*/, mp */*d*/, unsigned /*nbits*/, | |
98 | grand */*r*/, unsigned /*n*/, | |
99 | pgen_proc */*event*/, void */*ectx*/); | |
100 | ||
101 | /*----- That's all, folks -------------------------------------------------*/ | |
102 | ||
103 | #ifdef __cplusplus | |
104 | } | |
105 | #endif | |
106 | ||
107 | #endif |