Commit | Line | Data |
---|---|---|
a30942cc | 1 | /* -*-c-*- |
2 | * | |
a30942cc | 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 | /*----- Header files ------------------------------------------------------*/ |
29 | ||
30 | #include <mLib/dstr.h> | |
df5a67b8 | 31 | #include <mLib/macros.h> |
a30942cc | 32 | |
33 | #include "grand.h" | |
a30942cc | 34 | #include "mp.h" |
35 | #include "mpmont.h" | |
36 | #include "mprand.h" | |
37 | #include "pgen.h" | |
38 | #include "pfilt.h" | |
39 | #include "rabin.h" | |
40 | ||
41 | /*----- Main code ---------------------------------------------------------*/ | |
42 | ||
df5a67b8 MW |
43 | /* Oh, just shut up. */ |
44 | CLANG_WARNING("-Wempty-body") | |
45 | ||
052b36d0 | 46 | /* --- @strongprime_setup@ --- * |
a30942cc | 47 | * |
48 | * Arguments: @const char *name@ = pointer to name root | |
052b36d0 | 49 | * @mp *d@ = destination for search start point |
50 | * @pfilt *f@ = where to store filter jump context | |
a30942cc | 51 | * @unsigned nbits@ = number of bits wanted |
52 | * @grand *r@ = random number source | |
53 | * @unsigned n@ = number of attempts to make | |
54 | * @pgen_proc *event@ = event handler function | |
55 | * @void *ectx@ = argument for the event handler | |
56 | * | |
052b36d0 | 57 | * Returns: A starting point for a `strong' prime search, or zero. |
a30942cc | 58 | * |
052b36d0 | 59 | * Use: Sets up for a strong prime search, so that primes with |
60 | * particular properties can be found. It's probably important | |
61 | * to note that the number left in the filter context @f@ is | |
e62e86d3 MW |
62 | * congruent to 2 (mod 4); that the jump value is twice the |
63 | * product of two large primes; and that the starting point is | |
64 | * at least %$3 \cdot 2^{N-2}$%. (Hence, if you multiply two | |
65 | * such numbers, the product is at least | |
66 | * | |
67 | * %$9 \cdot 2^{2N-4} > 2^{2N-1}$% | |
68 | * | |
69 | * i.e., it will be (at least) a %$2 N$%-bit value. | |
a30942cc | 70 | */ |
71 | ||
052b36d0 | 72 | mp *strongprime_setup(const char *name, mp *d, pfilt *f, unsigned nbits, |
73 | grand *r, unsigned n, pgen_proc *event, void *ectx) | |
a30942cc | 74 | { |
052b36d0 | 75 | mp *s, *t, *q; |
a30942cc | 76 | dstr dn = DSTR_INIT; |
32bd36cf | 77 | unsigned slop, nb, u, i; |
a30942cc | 78 | |
052b36d0 | 79 | mp *rr = d; |
a30942cc | 80 | pgen_filterctx c; |
052b36d0 | 81 | pgen_jumpctx j; |
a30942cc | 82 | |
32bd36cf | 83 | /* --- Figure out how large the smaller primes should be --- * |
a30942cc | 84 | * |
32bd36cf MW |
85 | * We want them to be `as large as possible', subject to the constraint |
86 | * that we produce a number of the requested size at the end. This is | |
87 | * tricky, because the final prime search is going to involve quite large | |
88 | * jumps from its starting point; the size of the jumps are basically | |
89 | * determined by our choice here, and if they're too big then we won't find | |
90 | * a prime in time. | |
91 | * | |
92 | * Let's suppose we're trying to make an %$N$%-bit prime. The expected | |
93 | * number of steps tends to increase linearly with size, i.e., we need to | |
94 | * take about %2^k N$% steps for some %$k$%. If we're jumping by a | |
95 | * %$J$%-bit quantity each time, from an %$N$%-bit starting point, then we | |
96 | * will only be able to find a match if %$2^k N 2^{J-1} \le 2^{N-1}$%, | |
97 | * i.e., if %$J \le N - (k + \log_2 N)$%. | |
98 | * | |
99 | * Experimentation shows that taking %$k + \log_2 N = 12$% works well for | |
540ff246 | 100 | * %$N = 1024$%, so %$k = 2$%. Add a few extra bits for luck. |
a30942cc | 101 | */ |
102 | ||
32bd36cf | 103 | for (i = 1; i && nbits >> i; i <<= 1); assert(i); |
540ff246 | 104 | for (slop = 6, nb = nbits; nb > 1; i >>= 1) { |
32bd36cf MW |
105 | u = nb >> i; |
106 | if (u) { slop += i; nb = u; } | |
107 | } | |
108 | if (nbits/2 <= slop) return (0); | |
a30942cc | 109 | |
110 | /* --- Choose two primes %$s$% and %$t$% of half the required size --- */ | |
111 | ||
32bd36cf | 112 | nb = nbits/2 - slop; |
a30942cc | 113 | c.step = 1; |
114 | ||
0b09aab8 | 115 | rr = mprand(rr, nb, r, 1); |
a30942cc | 116 | DRESET(&dn); dstr_putf(&dn, "%s [s]", name); |
47566c4d | 117 | if ((s = pgen(dn.buf, MP_NEWSEC, rr, event, ectx, n, pgen_filter, &c, |
fbfcb6c0 | 118 | PGEN_BAILLIEPSWNTESTS, pgen_bailliepswtest, 0)) == 0) |
a30942cc | 119 | goto fail_s; |
a30942cc | 120 | |
0b09aab8 | 121 | rr = mprand(rr, nb, r, 1); |
a30942cc | 122 | DRESET(&dn); dstr_putf(&dn, "%s [t]", name); |
47566c4d | 123 | if ((t = pgen(dn.buf, MP_NEWSEC, rr, event, ectx, n, pgen_filter, &c, |
fbfcb6c0 | 124 | PGEN_BAILLIEPSWNTESTS, pgen_bailliepswtest, 0)) == 0) |
a30942cc | 125 | goto fail_t; |
a30942cc | 126 | |
bd9fe975 MW |
127 | /* --- Choose a suitable value for %$r = 2it + 1$% for some %$i$% --- * |
128 | * | |
129 | * Then %$r \equiv 1 \pmod{t}$%, i.e., %$r - 1$% is a multiple of %$t$%. | |
130 | */ | |
a30942cc | 131 | |
132 | rr = mp_lsl(rr, t, 1); | |
133 | pfilt_create(&c.f, rr); | |
32bd36cf | 134 | rr = mp_lsl(rr, rr, slop - 1); |
a30942cc | 135 | rr = mp_add(rr, rr, MP_ONE); |
136 | DRESET(&dn); dstr_putf(&dn, "%s [r]", name); | |
052b36d0 | 137 | j.j = &c.f; |
052b36d0 | 138 | q = pgen(dn.buf, MP_NEW, rr, event, ectx, n, pgen_jump, &j, |
fbfcb6c0 | 139 | PGEN_BAILLIEPSWNTESTS, pgen_bailliepswtest, 0); |
a30942cc | 140 | pfilt_destroy(&c.f); |
052b36d0 | 141 | if (!q) |
142 | goto fail_r; | |
a30942cc | 143 | |
e62e86d3 | 144 | /* --- Select a suitable congruence class for %$p$% --- * |
a30942cc | 145 | * |
bd9fe975 MW |
146 | * This computes %$p_0 = 2 s (s^{-1} \bmod r) - 1$%. Then %$p_0 + 1$% is |
147 | * clearly a multiple of %$s$%, and | |
148 | * | |
149 | * %$p_0 - 1 \equiv 2 s s^{-1} - 2 \equiv 0 \pmod{r}$% | |
150 | * | |
151 | * is a multiple of %$r$%. | |
a30942cc | 152 | */ |
153 | ||
bd490236 MW |
154 | rr = mp_modinv(rr, s, q); |
155 | rr = mp_mul(rr, rr, s); | |
156 | rr = mp_lsl(rr, rr, 1); | |
157 | rr = mp_sub(rr, rr, MP_ONE); | |
a30942cc | 158 | |
e62e86d3 MW |
159 | /* --- Pick a starting point for the search --- * |
160 | * | |
161 | * Select %$3 \cdot 2^{N-2} < p_1 < 2^N$% at random, only with | |
162 | * %$p_1 \equiv p_0 \pmod{2 r s}$. | |
163 | */ | |
a30942cc | 164 | |
165 | { | |
0b09aab8 | 166 | mp *x, *y; |
a30942cc | 167 | x = mp_mul(MP_NEW, q, s); |
168 | x = mp_lsl(x, x, 1); | |
e62e86d3 MW |
169 | pfilt_create(f, x); /* %$2 r s$% */ |
170 | y = mprand(MP_NEW, nbits, r, 0); | |
171 | y = mp_setbit(y, y, nbits - 2); | |
0b09aab8 MW |
172 | rr = mp_leastcongruent(rr, y, rr, x); |
173 | mp_drop(x); mp_drop(y); | |
a30942cc | 174 | } |
175 | ||
052b36d0 | 176 | /* --- Return the result --- */ |
a30942cc | 177 | |
a30942cc | 178 | mp_drop(q); |
052b36d0 | 179 | mp_drop(t); |
180 | mp_drop(s); | |
181 | dstr_destroy(&dn); | |
182 | return (rr); | |
183 | ||
184 | /* --- Tidy up if something failed --- */ | |
185 | ||
a30942cc | 186 | fail_r: |
a30942cc | 187 | mp_drop(t); |
188 | fail_t: | |
189 | mp_drop(s); | |
190 | fail_s: | |
191 | mp_drop(rr); | |
192 | dstr_destroy(&dn); | |
052b36d0 | 193 | return (0); |
a30942cc | 194 | } |
195 | ||
052b36d0 | 196 | /* --- @strongprime@ --- * |
197 | * | |
198 | * Arguments: @const char *name@ = pointer to name root | |
199 | * @mp *d@ = destination integer | |
200 | * @unsigned nbits@ = number of bits wanted | |
201 | * @grand *r@ = random number source | |
202 | * @unsigned n@ = number of attempts to make | |
203 | * @pgen_proc *event@ = event handler function | |
204 | * @void *ectx@ = argument for the event handler | |
205 | * | |
206 | * Returns: A `strong' prime, or zero. | |
207 | * | |
208 | * Use: Finds `strong' primes. A strong prime %$p$% is such that | |
209 | * | |
210 | * * %$p - 1$% has a large prime factor %$r$%, | |
211 | * * %$p + 1$% has a large prime factor %$s$%, and | |
212 | * * %$r - 1$% has a large prime factor %$t$%. | |
052b36d0 | 213 | */ |
214 | ||
215 | mp *strongprime(const char *name, mp *d, unsigned nbits, grand *r, | |
216 | unsigned n, pgen_proc *event, void *ectx) | |
217 | { | |
285bf989 | 218 | mp *p; |
052b36d0 | 219 | pfilt f; |
220 | pgen_jumpctx j; | |
45c0fd36 | 221 | |
285bf989 MW |
222 | if (d) mp_copy(d); |
223 | p = strongprime_setup(name, d, &f, nbits, r, n, event, ectx); | |
224 | if (!p) { mp_drop(d); return (0); } | |
052b36d0 | 225 | j.j = &f; |
285bf989 | 226 | p = pgen(name, p, p, event, ectx, n, pgen_jump, &j, |
fbfcb6c0 | 227 | PGEN_BAILLIEPSWNTESTS, pgen_bailliepswtest, 0); |
32bd36cf | 228 | if (mp_bits(p) != nbits) { mp_drop(p); return (0); } |
052b36d0 | 229 | pfilt_destroy(&f); |
285bf989 MW |
230 | mp_drop(d); |
231 | return (p); | |
052b36d0 | 232 | } |
233 | ||
a30942cc | 234 | /*----- That's all, folks -------------------------------------------------*/ |