1 /* bignum-random-prime.c
2 *
3 * Generation of random provable primes.
4 */
5
6 /* Copyright (C) 2013 Red Hat
7 *
8 * The nettle library is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU Lesser General Public License as published by
10 * the Free Software Foundation; either version 2.1 of the License, or (at your
11 * option) any later version.
12 *
13 * The nettle library is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
16 * License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public License
19 * along with the nettle library; see the file COPYING.LIB. If not, write to
20 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
21 * MA 02111-1301, USA.
22 */
23
24 #if HAVE_CONFIG_H
25 #include <config.h>
26 #endif
27
28 #include <assert.h>
29 #include <stdlib.h>
30 #include <nettle/memxor.h>
31 #include <nettle/bignum.h>
32 #include <dsa-fips.h>
33
34 #include <nettle/macros.h>
35
36 static const uint16_t primes[] = {
37 3, 5, 7, 11, 13, 17, 19,
38 23, 29, 31, 37, 41, 43, 47,
39 53, 59, 61, 67, 71, 73, 79,
40 83, 89, 97, 101, 103, 107, 109,
41 113, 127, 131, 137, 139, 149, 151,
42 157, 163, 167, 173, 179, 181, 191,
43 193, 197, 199, 211, 223, 227, 229,
44 233, 239, 241, 251, 257, 263, 269,
45 271, 277, 281, 283, 293, 307, 311,
46 313, 317, 331, 337, 347, 349, 353,
47 359, 367, 373, 379, 383, 389, 397,
48 401, 409, 419, 421, 431, 433, 439,
49 443, 449, 457, 461, 463, 467, 479,
50 487, 491, 499, 503, 509, 521, 523,
51 541, 547, 557, 563, 569, 571, 577,
52 587, 593, 599, 601, 607, 613, 617,
53 619, 631, 641, 643, 647, 653, 659,
54 661, 673, 677, 683, 691, 701, 709,
55 719, 727, 733, 739, 743, 751, 757,
56 761, 769, 773, 787, 797, 809, 811,
57 821, 823, 827, 829, 839, 853, 857,
58 859, 863, 877, 881, 883, 887, 907,
59 911, 919, 929, 937, 941, 947, 953,
60 967, 971, 977, 983, 991, 997, 1009,
61 1013, 1019, 1021, 1031, 1033, 1039, 1049,
62 1051, 1061, 1063, 1069, 1087, 1091, 1093,
63 1097, 1103, 1109, 1117, 1123, 1129, 1151,
64 1153, 1163, 1171, 1181, 1187, 1193, 1201,
65 1213, 1217, 1223, 1229, 1231, 1237, 1249,
66 1259, 1277, 1279, 1283, 1289, 1291, 1297,
67 1301, 1303, 1307, 1319, 1321, 1327, 1361,
68 1367, 1373, 1381, 1399, 1409, 1423, 1427,
69 1429, 1433, 1439, 1447, 1451, 1453, 1459,
70 1471, 1481, 1483, 1487, 1489, 1493, 1499,
71 1511, 1523, 1531, 1543, 1549, 1553, 1559,
72 1567, 1571, 1579, 1583, 1597, 1601, 1607,
73 1609, 1613, 1619, 1621, 1627, 1637, 1657,
74 1663, 1667, 1669, 1693, 1697, 1699, 1709,
75 1721, 1723, 1733, 1741, 1747, 1753, 1759,
76 1777, 1783, 1787, 1789, 1801, 1811, 1823,
77 1831, 1847, 1861, 1867, 1871, 1873, 1877,
78 1879, 1889, 1901, 1907, 1913, 1931, 1933,
79 1949, 1951, 1973, 1979, 1987, 1993, 1997,
80 1999, 2003, 2011, 2017, 2027, 2029, 2039,
81 2053, 2063, 2069, 2081, 2083, 2087, 2089,
82 2099, 2111, 2113, 2129, 2131, 2137, 2141,
83 2143, 2153, 2161, 2179, 2203, 2207, 2213,
84 2221, 2237, 2239, 2243, 2251, 2267, 2269,
85 2273, 2281, 2287, 2293, 2297, 2309, 2311,
86 2333, 2339, 2341, 2347, 2351, 2357, 2371,
87 2377, 2381, 2383, 2389, 2393, 2399, 2411,
88 2417, 2423, 2437, 2441, 2447, 2459, 2467,
89 2473, 2477, 2503, 2521, 2531, 2539, 2543,
90 2549, 2551, 2557, 2579, 2591, 2593, 2609,
91 2617, 2621, 2633, 2647, 2657, 2659, 2663,
92 2671, 2677, 2683, 2687, 2689, 2693, 2699,
93 2707, 2711, 2713, 2719, 2729, 2731, 2741,
94 2749, 2753, 2767, 2777, 2789, 2791, 2797,
95 2801, 2803, 2819, 2833, 2837, 2843, 2851,
96 2857, 2861, 2879, 2887, 2897, 2903, 2909,
97 2917, 2927, 2939, 2953, 2957, 2963, 2969,
98 2971, 2999, 3001, 3011, 3019, 3023, 3037,
99 3041, 3049, 3061, 3067, 3079, 3083, 3089,
100 3109, 3119, 3121, 3137, 3163, 3167, 3169,
101 3181, 3187, 3191, 3203, 3209, 3217, 3221,
102 3229, 3251, 3253, 3257, 3259, 3271, 3299,
103 3301, 3307, 3313, 3319, 3323, 3329, 3331,
104 3343, 3347, 3359, 3361, 3371, 3373, 3389,
105 3391, 3407, 3413, 3433, 3449, 3457, 3461,
106 3463, 3467, 3469, 3491, 3499, 3511, 3517,
107 3527, 3529, 3533, 3539, 3541, 3547, 3557,
108 3559, 3571, 3581, 3583, 3593, 3607, 3613,
109 3617, 3623, 3631, 3637, 3643, 3659, 3671,
110 3673, 3677, 3691, 3697, 3701, 3709, 3719,
111 3727, 3733, 3739, 3761, 3767, 3769, 3779,
112 3793, 3797, 3803, 3821, 3823, 3833, 3847,
113 3851, 3853, 3863, 3877, 3881, 3889, 3907,
114 3911, 3917, 3919, 3923, 3929, 3931, 3943,
115 3947, 3967, 3989, 4001, 4003, 4007, 4013,
116 4019, 4021, 4027, 4049, 4051, 4057, 4073,
117 4079, 4091, 4093, 4099, 4111, 4127, 4129,
118 4133, 4139, 4153, 4157, 4159, 4177, 4201,
119 4211, 4217, 4219, 4229, 4231, 4241, 4243,
120 4253, 4259, 4261, 4271, 4273, 4283, 4289,
121 4297, 4327, 4337, 4339, 4349, 4357, 4363,
122 4373, 4391, 4397, 4409, 4421, 4423, 4441,
123 4447, 4451, 4457, 4463, 4481, 4483, 4493,
124 4507, 4513, 4517, 4519, 4523, 4547, 4549,
125 4561, 4567, 4583, 4591, 4597, 4603, 4621,
126 4637, 4639, 4643, 4649, 4651, 4657, 4663,
127 4673, 4679, 4691, 4703, 4721, 4723, 4729,
128 4733, 4751, 4759, 4783, 4787, 4789, 4793,
129 4799, 4801, 4813, 4817, 4831, 4861, 4871,
130 4877, 4889, 4903, 4909, 4919, 4931, 4933,
131 4937, 4943, 4951, 4957, 4967, 4969, 4973,
132 4987, 4993, 4999, 5003, 5009, 5011, 5021,
133 5023, 5039, 5051, 5059, 5077, 5081, 5087,
134 5099, 5101, 5107, 5113, 5119, 5147, 5153,
135 5167, 5171, 5179, 5189, 5197, 5209, 5227,
136 5231, 5233, 5237, 5261, 5273, 5279, 5281,
137 5297, 5303, 5309, 5323, 5333, 5347, 5351,
138 5381, 5387, 5393, 5399, 5407, 5413, 5417,
139 5419, 5431, 5437, 5441, 5443, 5449, 5471,
140 5477, 5479, 5483, 5501, 5503, 5507, 5519,
141 5521, 5527, 5531, 5557, 5563, 5569, 5573,
142 5581, 5591, 5623, 5639, 5641, 5647, 5651,
143 5653, 5657, 5659, 5669, 5683, 5689, 5693,
144 5701, 5711, 5717, 5737, 5741, 5743, 5749,
145 5779, 5783, 5791, 5801, 5807, 5813, 5821,
146 5827, 5839, 5843, 5849, 5851, 5857, 5861,
147 5867, 5869, 5879, 5881, 5897, 5903, 5923,
148 5927, 5939, 5953, 5981, 5987, 6007, 6011,
149 6029, 6037, 6043, 6047, 6053, 6067, 6073,
150 6079, 6089, 6091, 6101, 6113, 6121, 6131,
151 6133, 6143, 6151, 6163, 6173, 6197, 6199,
152 6203, 6211, 6217, 6221, 6229, 6247, 6257,
153 6263, 6269, 6271, 6277, 6287, 6299, 6301,
154 6311, 6317, 6323, 6329, 6337, 6343, 6353,
155 6359, 6361, 6367, 6373, 6379, 6389, 6397,
156 6421, 6427, 6449, 6451, 6469, 6473, 6481,
157 6491, 6521, 6529, 6547, 6551, 6553, 6563,
158 6569, 6571, 6577, 6581, 6599, 6607, 6619,
159 6637, 6653, 6659, 6661, 6673, 6679, 6689,
160 6691, 6701, 6703, 6709, 6719, 6733, 6737,
161 6761, 6763, 6779, 6781, 6791, 6793, 6803,
162 6823, 6827, 6829, 6833, 6841, 6857, 6863,
163 6869, 6871, 6883, 6899, 6907, 6911, 6917,
164 6947, 6949, 6959, 6961, 6967, 6971, 6977,
165 6983, 6991, 6997, 7001, 7013, 7019, 7027,
166 7039, 7043, 7057, 7069, 7079, 7103, 7109,
167 7121, 7127, 7129, 7151, 7159, 7177, 7187,
168 7193, 7207, 7211, 7213, 7219, 7229, 7237,
169 7243, 7247, 7253, 7283, 7297, 7307, 7309,
170 7321, 7331, 7333, 7349, 7351, 7369, 7393,
171 7411, 7417, 7433, 7451, 7457, 7459, 7477,
172 7481, 7487, 7489, 7499, 7507, 7517, 7523,
173 7529, 7537, 7541, 7547, 7549, 7559, 7561,
174 7573, 7577, 7583, 7589, 7591, 7603, 7607,
175 7621, 7639, 7643, 7649, 7669, 7673, 7681,
176 7687, 7691, 7699, 7703, 7717, 7723, 7727,
177 7741, 7753, 7757, 7759, 7789, 7793, 7817,
178 7823, 7829, 7841, 7853, 7867, 7873, 7877,
179 7879, 7883, 7901, 7907, 7919, 7927, 7933,
180 7937, 7949, 7951, 7963, 7993, 8009, 8011,
181 8017, 8039, 8053, 8059, 8069, 8081, 8087,
182 8089, 8093, 8101, 8111, 8117, 8123, 8147,
183 8161, 8167, 8171, 8179, 8191, 8209, 8219,
184 8221, 8231, 8233, 8237, 8243, 8263, 8269,
185 8273, 8287, 8291, 8293, 8297, 8311, 8317,
186 8329, 8353, 8363, 8369, 8377, 8387, 8389,
187 8419, 8423, 8429, 8431, 8443, 8447, 8461,
188 8467, 8501, 8513, 8521, 8527, 8537, 8539,
189 8543, 8563, 8573, 8581, 8597, 8599, 8609,
190 8623, 8627, 8629, 8641, 8647, 8663, 8669,
191 8677, 8681, 8689, 8693, 8699, 8707, 8713,
192 8719, 8731, 8737, 8741, 8747, 8753, 8761,
193 8779, 8783, 8803, 8807, 8819, 8821, 8831,
194 8837, 8839, 8849, 8861, 8863, 8867, 8887,
195 8893, 8923, 8929, 8933, 8941, 8951, 8963,
196 8969, 8971, 8999, 9001, 9007, 9011, 9013,
197 9029, 9041, 9043, 9049, 9059, 9067, 9091,
198 9103, 9109, 9127, 9133, 9137, 9151, 9157,
199 9161, 9173, 9181, 9187, 9199, 9203, 9209,
200 9221, 9227, 9239, 9241, 9257, 9277, 9281,
201 9283, 9293, 9311, 9319, 9323, 9337, 9341,
202 9343, 9349, 9371, 9377, 9391, 9397, 9403,
203 9413, 9419, 9421, 9431, 9433, 9437, 9439,
204 9461, 9463, 9467, 9473, 9479, 9491, 9497,
205 9511, 9521, 9533, 9539, 9547, 9551, 9587,
206 9601, 9613, 9619, 9623, 9629, 9631, 9643,
207 9649, 9661, 9677, 9679, 9689, 9697, 9719,
208 9721, 9733, 9739, 9743, 9749, 9767, 9769,
209 9781, 9787, 9791, 9803, 9811, 9817, 9829,
210 9833, 9839, 9851, 9857, 9859, 9871, 9883,
211 9887, 9901, 9907, 9923, 9929, 9931, 9941,
212 9949, 9967, 9973, 10007, 10009, 10037, 10039,
213 10061, 10067, 10069, 10079, 10091, 10093, 10099,
214 10103, 10111, 10133, 10139, 10141, 10151, 10159,
215 10163, 10169, 10177, 10181, 10193, 10211, 10223,
216 10243, 10247, 10253, 10259, 10267, 10271, 10273,
217 10289, 10301, 10303, 10313, 10321, 10331, 10333,
218 10337, 10343, 10357, 10369, 10391, 10399, 10427,
219 10429, 10433, 10453, 10457, 10459, 10463, 10477,
220 10487, 10499, 10501, 10513, 10529, 10531, 10559,
221 10567, 10589, 10597, 10601, 10607, 10613, 10627,
222 10631, 10639, 10651, 10657, 10663, 10667, 10687,
223 10691, 10709, 10711, 10723, 10729, 10733, 10739,
224 10753, 10771, 10781, 10789, 10799, 10831, 10837,
225 10847, 10853, 10859, 10861, 10867, 10883, 10889,
226 10891, 10903, 10909, 10937, 10939, 10949, 10957,
227 10973, 10979, 10987, 10993, 11003, 11027, 11047,
228 11057, 11059, 11069, 11071, 11083, 11087, 11093,
229 11113, 11117, 11119, 11131, 11149, 11159, 11161,
230 11171, 11173, 11177, 11197, 11213, 11239, 11243,
231 11251, 11257, 11261, 11273, 11279, 11287, 11299,
232 11311, 11317, 11321, 11329, 11351, 11353, 11369,
233 11383, 11393, 11399, 11411, 11423, 11437, 11443,
234 11447, 11467, 11471, 11483, 11489, 11491, 11497,
235 11503, 11519, 11527, 11549, 11551, 11579, 11587,
236 11593, 11597, 11617, 11621, 11633, 11657, 11677,
237 11681, 11689, 11699, 11701, 11717, 11719, 11731,
238 11743, 11777, 11779, 11783, 11789, 11801, 11807,
239 11813, 11821, 11827, 11831, 11833, 11839, 11863,
240 11867, 11887, 11897, 11903, 11909, 11923, 11927,
241 11933, 11939, 11941, 11953, 11959, 11969, 11971,
242 11981, 11987, 12007, 12011, 12037, 12041, 12043,
243 12049, 12071, 12073, 12097, 12101, 12107, 12109,
244 12113, 12119, 12143, 12149, 12157, 12161, 12163,
245 12197, 12203, 12211, 12227, 12239, 12241, 12251,
246 12253, 12263, 12269, 12277, 12281, 12289, 12301,
247 12323, 12329, 12343, 12347, 12373, 12377, 12379,
248 12391, 12401, 12409, 12413, 12421, 12433, 12437,
249 12451, 12457, 12473, 12479, 12487, 12491, 12497,
250 12503, 12511, 12517, 12527, 12539, 12541, 12547,
251 12553, 12569, 12577, 12583, 12589, 12601, 12611,
252 12613, 12619, 12637, 12641, 12647, 12653, 12659,
253 12671, 12689, 12697, 12703, 12713, 12721, 12739,
254 12743, 12757, 12763, 12781, 12791, 12799, 12809,
255 12821, 12823, 12829, 12841, 12853, 12889, 12893,
256 12899, 12907, 12911, 12917, 12919, 12923, 12941,
257 12953, 12959, 12967, 12973, 12979, 12983, 13001,
258 13003, 13007, 13009, 13033, 13037, 13043, 13049,
259 13063, 13093, 13099, 13103, 13109, 13121, 13127,
260 13147, 13151, 13159, 13163, 13171, 13177, 13183,
261 13187, 13217, 13219, 13229, 13241, 13249, 13259,
262 13267, 13291, 13297, 13309, 13313, 13327, 13331,
263 13337, 13339, 13367, 13381, 13397, 13399, 13411,
264 13417, 13421, 13441, 13451, 13457, 13463, 13469,
265 13477, 13487, 13499, 13513, 13523, 13537, 13553,
266 13567, 13577, 13591, 13597, 13613, 13619, 13627,
267 13633, 13649, 13669, 13679, 13681, 13687, 13691,
268 13693, 13697, 13709, 13711, 13721, 13723, 13729,
269 13751, 13757, 13759, 13763, 13781, 13789, 13799,
270 13807, 13829, 13831, 13841, 13859, 13873, 13877,
271 13879, 13883, 13901, 13903, 13907, 13913, 13921,
272 13931, 13933, 13963, 13967, 13997, 13999, 14009,
273 14011, 14029, 14033, 14051, 14057, 14071, 14081,
274 14083, 14087, 14107, 14143, 14149, 14153, 14159,
275 14173, 14177, 14197, 14207, 14221, 14243, 14249,
276 14251, 14281, 14293, 14303, 14321, 14323, 14327,
277 14341, 14347, 14369, 14387, 14389, 14401, 14407,
278 14411, 14419, 14423, 14431, 14437, 14447, 14449,
279 14461, 14479, 14489, 14503, 14519, 14533, 14537,
280 14543, 14549, 14551, 14557, 14561, 14563, 14591,
281 14593, 14621, 14627, 14629, 14633, 14639, 14653,
282 14657, 14669, 14683, 14699, 14713, 14717, 14723,
283 14731, 14737, 14741, 14747, 14753, 14759, 14767,
284 14771, 14779, 14783, 14797, 14813, 14821, 14827,
285 14831, 14843, 14851, 14867, 14869, 14879, 14887,
286 14891, 14897, 14923, 14929, 14939, 14947, 14951,
287 14957, 14969, 14983, 15013, 15017, 15031, 15053,
288 15061, 15073, 15077, 15083, 15091, 15101, 15107,
289 15121, 15131, 15137, 15139, 15149, 15161, 15173,
290 15187, 15193, 15199, 15217, 15227, 15233, 15241,
291 15259, 15263, 15269, 15271, 15277, 15287, 15289,
292 15299, 15307, 15313, 15319, 15329, 15331, 15349,
293 15359, 15361, 15373, 15377, 15383, 15391, 15401,
294 15413, 15427, 15439, 15443, 15451, 15461, 15467,
295 15473, 15493, 15497, 15511, 15527, 15541, 15551,
296 15559, 15569, 15581, 15583, 15601, 15607, 15619,
297 15629, 15641, 15643, 15647, 15649, 15661, 15667,
298 15671, 15679, 15683, 15727, 15731, 15733, 15737,
299 15739, 15749, 15761, 15767, 15773, 15787, 15791,
300 15797, 15803, 15809, 15817, 15823, 15859, 15877,
301 15881, 15887, 15889, 15901, 15907, 15913, 15919,
302 15923, 15937, 15959, 15971, 15973, 15991, 16001,
303 16007, 16033, 16057, 16061, 16063, 16067, 16069,
304 16073, 16087, 16091, 16097, 16103, 16111, 16127,
305 16139, 16141, 16183, 16187, 16189, 16193, 16217,
306 16223, 16229, 16231, 16249, 16253, 16267, 16273,
307 16301, 16319, 16333, 16339, 16349, 16361, 16363,
308 16369, 16381, 16411, 16417, 16421, 16427, 16433,
309 16447, 16451, 16453, 16477, 16481, 16487, 16493,
310 16519, 16529, 16547, 16553, 16561, 16567, 16573,
311 16603, 16607, 16619, 16631, 16633, 16649, 16651,
312 16657, 16661, 16673, 16691, 16693, 16699, 16703,
313 16729, 16741, 16747, 16759, 16763, 16787, 16811,
314 16823, 16829, 16831, 16843, 16871, 16879, 16883,
315 16889, 16901, 16903, 16921, 16927, 16931, 16937,
316 16943, 16963, 16979, 16981, 16987, 16993, 17011,
317 17021, 17027, 17029, 17033, 17041, 17047, 17053,
318 17077, 17093, 17099, 17107, 17117, 17123, 17137,
319 17159, 17167, 17183, 17189, 17191, 17203, 17207,
320 17209, 17231, 17239, 17257, 17291, 17293, 17299,
321 17317, 17321, 17327, 17333, 17341, 17351, 17359,
322 17377, 17383, 17387, 17389, 17393, 17401, 17417,
323 17419, 17431, 17443, 17449, 17467, 17471, 17477,
324 17483, 17489, 17491, 17497, 17509, 17519, 17539,
325 17551, 17569, 17573, 17579, 17581, 17597, 17599,
326 17609, 17623, 17627, 17657, 17659, 17669, 17681,
327 17683, 17707, 17713, 17729, 17737, 17747, 17749,
328 17761, 17783, 17789, 17791, 17807, 17827, 17837,
329 17839, 17851, 17863, 17881, 17891, 17903, 17909,
330 17911, 17921, 17923, 17929, 17939, 17957, 17959,
331 17971, 17977, 17981, 17987, 17989, 18013, 18041,
332 18043, 18047, 18049, 18059, 18061, 18077, 18089,
333 18097, 18119, 18121, 18127, 18131, 18133, 18143,
334 18149, 18169, 18181, 18191, 18199, 18211, 18217,
335 18223, 18229, 18233, 18251, 18253, 18257, 18269,
336 18287, 18289, 18301, 18307, 18311, 18313, 18329,
337 18341, 18353, 18367, 18371, 18379, 18397, 18401,
338 18413, 18427, 18433, 18439, 18443, 18451, 18457,
339 18461, 18481, 18493, 18503, 18517, 18521, 18523,
340 18539, 18541, 18553, 18583, 18587, 18593, 18617,
341 18637, 18661, 18671, 18679, 18691, 18701, 18713,
342 18719, 18731, 18743, 18749, 18757, 18773, 18787,
343 18793, 18797, 18803, 18839, 18859, 18869, 18899,
344 18911, 18913, 18917, 18919, 18947, 18959, 18973,
345 18979, 19001, 19009, 19013, 19031, 19037, 19051,
346 19069, 19073, 19079, 19081, 19087, 19121, 19139,
347 19141, 19157, 19163, 19181, 19183, 19207, 19211,
348 19213, 19219, 19231, 19237, 19249, 19259, 19267,
349 19273, 19289, 19301, 19309, 19319, 19333, 19373,
350 19379, 19381, 19387, 19391, 19403, 19417, 19421,
351 19423, 19427, 19429, 19433, 19441, 19447, 19457,
352 19463, 19469, 19471, 19477, 19483, 19489, 19501,
353 19507, 19531, 19541, 19543, 19553, 19559, 19571,
354 19577, 19583, 19597, 19603, 19609, 19661, 19681,
355 19687, 19697, 19699, 19709, 19717, 19727, 19739,
356 19751, 19753, 19759, 19763, 19777, 19793, 19801,
357 19813, 19819, 19841, 19843, 19853, 19861, 19867,
358 19889, 19891, 19913, 19919, 19927, 19937, 19949,
359 19961, 19963, 19973, 19979, 19991, 19993, 19997,
360 20011, 20021, 20023, 20029, 20047, 20051, 20063,
361 20071, 20089, 20101, 20107, 20113, 20117, 20123,
362 20129, 20143, 20147, 20149, 20161, 20173, 20177,
363 20183, 20201, 20219, 20231, 20233, 20249, 20261,
364 20269, 20287, 20297, 20323, 20327, 20333, 20341,
365 20347, 20353, 20357, 20359, 20369, 20389, 20393,
366 20399, 20407, 20411, 20431, 20441, 20443, 20477,
367 20479, 20483, 20507, 20509, 20521, 20533, 20543,
368 20549, 20551, 20563, 20593, 20599, 20611, 20627,
369 20639, 20641, 20663, 20681, 20693, 20707, 20717,
370 20719, 20731, 20743, 20747, 20749, 20753, 20759,
371 20771, 20773, 20789, 20807, 20809, 20849, 20857,
372 20873, 20879, 20887, 20897, 20899, 20903, 20921,
373 20929, 20939, 20947, 20959, 20963, 20981, 20983,
374 21001, 21011, 21013, 21017, 21019, 21023, 21031,
375 21059, 21061, 21067, 21089, 21101, 21107, 21121,
376 21139, 21143, 21149, 21157, 21163, 21169, 21179,
377 21187, 21191, 21193, 21211, 21221, 21227, 21247,
378 21269, 21277, 21283, 21313, 21317, 21319, 21323,
379 21341, 21347, 21377, 21379, 21383, 21391, 21397,
380 21401, 21407, 21419, 21433, 21467, 21481, 21487,
381 21491, 21493, 21499, 21503, 21517, 21521, 21523,
382 21529, 21557, 21559, 21563, 21569, 21577, 21587,
383 21589, 21599, 21601, 21611, 21613, 21617, 21647,
384 21649, 21661, 21673, 21683, 21701, 21713, 21727,
385 21737, 21739, 21751, 21757, 21767, 21773, 21787,
386 21799, 21803, 21817, 21821, 21839, 21841, 21851,
387 21859, 21863, 21871, 21881, 21893, 21911, 21929,
388 21937, 21943, 21961, 21977, 21991, 21997, 22003,
389 22013, 22027, 22031, 22037, 22039, 22051, 22063,
390 22067, 22073, 22079, 22091, 22093, 22109, 22111,
391 22123, 22129, 22133, 22147, 22153, 22157, 22159,
392 22171, 22189, 22193, 22229, 22247, 22259, 22271,
393 22273, 22277, 22279, 22283, 22291, 22303, 22307,
394 22343, 22349, 22367, 22369, 22381, 22391, 22397,
395 22409, 22433, 22441, 22447, 22453, 22469, 22481,
396 22483, 22501, 22511, 22531, 22541, 22543, 22549,
397 22567, 22571, 22573, 22613, 22619, 22621, 22637,
398 22639, 22643, 22651, 22669, 22679, 22691, 22697,
399 22699, 22709, 22717, 22721, 22727, 22739, 22741,
400 22751, 22769, 22777, 22783, 22787, 22807, 22811,
401 22817, 22853, 22859, 22861, 22871, 22877, 22901,
402 22907, 22921, 22937, 22943, 22961, 22963, 22973,
403 22993, 23003, 23011, 23017, 23021, 23027, 23029,
404 23039, 23041, 23053, 23057, 23059, 23063, 23071,
405 23081, 23087, 23099, 23117, 23131, 23143, 23159,
406 23167, 23173, 23189, 23197, 23201, 23203, 23209,
407 23227, 23251, 23269, 23279, 23291, 23293, 23297,
408 23311, 23321, 23327, 23333, 23339, 23357, 23369,
409 23371, 23399, 23417, 23431, 23447, 23459, 23473,
410 23497, 23509, 23531, 23537, 23539, 23549, 23557,
411 23561, 23563, 23567, 23581, 23593, 23599, 23603,
412 23609, 23623, 23627, 23629, 23633, 23663, 23669,
413 23671, 23677, 23687, 23689, 23719, 23741, 23743,
414 23747, 23753, 23761, 23767, 23773, 23789, 23801,
415 23813, 23819, 23827, 23831, 23833, 23857, 23869,
416 23873, 23879, 23887, 23893, 23899, 23909, 23911,
417 23917, 23929, 23957, 23971, 23977, 23981, 23993,
418 24001, 24007, 24019, 24023, 24029, 24043, 24049,
419 24061, 24071, 24077, 24083, 24091, 24097, 24103,
420 24107, 24109, 24113, 24121, 24133, 24137, 24151,
421 24169, 24179, 24181, 24197, 24203, 24223, 24229,
422 24239, 24247, 24251, 24281, 24317, 24329, 24337,
423 24359, 24371, 24373, 24379, 24391, 24407, 24413,
424 24419, 24421, 24439, 24443, 24469, 24473, 24481,
425 24499, 24509, 24517, 24527, 24533, 24547, 24551,
426 24571, 24593, 24611, 24623, 24631, 24659, 24671,
427 24677, 24683, 24691, 24697, 24709, 24733, 24749,
428 24763, 24767, 24781, 24793, 24799, 24809, 24821,
429 24841, 24847, 24851, 24859, 24877, 24889, 24907,
430 24917, 24919, 24923, 24943, 24953, 24967, 24971,
431 24977, 24979, 24989, 25013, 25031, 25033, 25037,
432 25057, 25073, 25087, 25097, 25111, 25117, 25121,
433 25127, 25147, 25153, 25163, 25169, 25171, 25183,
434 25189, 25219, 25229, 25237, 25243, 25247, 25253,
435 25261, 25301, 25303, 25307, 25309, 25321, 25339,
436 25343, 25349, 25357, 25367, 25373, 25391, 25409,
437 25411, 25423, 25439, 25447, 25453, 25457, 25463,
438 25469, 25471, 25523, 25537, 25541, 25561, 25577,
439 25579, 25583, 25589, 25601, 25603, 25609, 25621,
440 25633, 25639, 25643, 25657, 25667, 25673, 25679,
441 25693, 25703, 25717, 25733, 25741, 25747, 25759,
442 25763, 25771, 25793, 25799, 25801, 25819, 25841,
443 25847, 25849, 25867, 25873, 25889, 25903, 25913,
444 25919, 25931, 25933, 25939, 25943, 25951, 25969,
445 25981, 25997, 25999, 26003, 26017, 26021, 26029,
446 26041, 26053, 26083, 26099, 26107, 26111, 26113,
447 26119, 26141, 26153, 26161, 26171, 26177, 26183,
448 26189, 26203, 26209, 26227, 26237, 26249, 26251,
449 26261, 26263, 26267, 26293, 26297, 26309, 26317,
450 26321, 26339, 26347, 26357, 26371, 26387, 26393,
451 26399, 26407, 26417, 26423, 26431, 26437, 26449,
452 26459, 26479, 26489, 26497, 26501, 26513, 26539,
453 26557, 26561, 26573, 26591, 26597, 26627, 26633,
454 26641, 26647, 26669, 26681, 26683, 26687, 26693,
455 26699, 26701, 26711, 26713, 26717, 26723, 26729,
456 26731, 26737, 26759, 26777, 26783, 26801, 26813,
457 26821, 26833, 26839, 26849, 26861, 26863, 26879,
458 26881, 26891, 26893, 26903, 26921, 26927, 26947,
459 26951, 26953, 26959, 26981, 26987, 26993, 27011,
460 27017, 27031, 27043, 27059, 27061, 27067, 27073,
461 27077, 27091, 27103, 27107, 27109, 27127, 27143,
462 27179, 27191, 27197, 27211, 27239, 27241, 27253,
463 27259, 27271, 27277, 27281, 27283, 27299, 27329,
464 27337, 27361, 27367, 27397, 27407, 27409, 27427,
465 27431, 27437, 27449, 27457, 27479, 27481, 27487,
466 27509, 27527, 27529, 27539, 27541, 27551, 27581,
467 27583, 27611, 27617, 27631, 27647, 27653, 27673,
468 27689, 27691, 27697, 27701, 27733, 27737, 27739,
469 27743, 27749, 27751, 27763, 27767, 27773, 27779,
470 27791, 27793, 27799, 27803, 27809, 27817, 27823,
471 27827, 27847, 27851, 27883, 27893, 27901, 27917,
472 27919, 27941, 27943, 27947, 27953, 27961, 27967,
473 27983, 27997, 28001, 28019, 28027, 28031, 28051,
474 28057, 28069, 28081, 28087, 28097, 28099, 28109,
475 28111, 28123, 28151, 28163, 28181, 28183, 28201,
476 28211, 28219, 28229, 28277, 28279, 28283, 28289,
477 28297, 28307, 28309, 28319, 28349, 28351, 28387,
478 28393, 28403, 28409, 28411, 28429, 28433, 28439,
479 28447, 28463, 28477, 28493, 28499, 28513, 28517,
480 28537, 28541, 28547, 28549, 28559, 28571, 28573,
481 28579, 28591, 28597, 28603, 28607, 28619, 28621,
482 28627, 28631, 28643, 28649, 28657, 28661, 28663,
483 28669, 28687, 28697, 28703, 28711, 28723, 28729,
484 28751, 28753, 28759, 28771, 28789, 28793, 28807,
485 28813, 28817, 28837, 28843, 28859, 28867, 28871,
486 28879, 28901, 28909, 28921, 28927, 28933, 28949,
487 28961, 28979, 29009, 29017, 29021, 29023, 29027,
488 29033, 29059, 29063, 29077, 29101, 29123, 29129,
489 29131, 29137, 29147, 29153, 29167, 29173, 29179,
490 29191, 29201, 29207, 29209, 29221, 29231, 29243,
491 29251, 29269, 29287, 29297, 29303, 29311, 29327,
492 29333, 29339, 29347, 29363, 29383, 29387, 29389,
493 29399, 29401, 29411, 29423, 29429, 29437, 29443,
494 29453, 29473, 29483, 29501, 29527, 29531, 29537,
495 29567, 29569, 29573, 29581, 29587, 29599, 29611,
496 29629, 29633, 29641, 29663, 29669, 29671, 29683,
497 29717, 29723, 29741, 29753, 29759, 29761, 29789,
498 29803, 29819, 29833, 29837, 29851, 29863, 29867,
499 29873, 29879, 29881, 29917, 29921, 29927, 29947,
500 29959, 29983, 29989, 30011, 30013, 30029, 30047,
501 30059, 30071, 30089, 30091, 30097, 30103, 30109,
502 30113, 30119, 30133, 30137, 30139, 30161, 30169,
503 30181, 30187, 30197, 30203, 30211, 30223, 30241,
504 30253, 30259, 30269, 30271, 30293, 30307, 30313,
505 30319, 30323, 30341, 30347, 30367, 30389, 30391,
506 30403, 30427, 30431, 30449, 30467, 30469, 30491,
507 30493, 30497, 30509, 30517, 30529, 30539, 30553,
508 30557, 30559, 30577, 30593, 30631, 30637, 30643,
509 30649, 30661, 30671, 30677, 30689, 30697, 30703,
510 30707, 30713, 30727, 30757, 30763, 30773, 30781,
511 30803, 30809, 30817, 30829, 30839, 30841, 30851,
512 30853, 30859, 30869, 30871, 30881, 30893, 30911,
513 30931, 30937, 30941, 30949, 30971, 30977, 30983,
514 31013, 31019, 31033, 31039, 31051, 31063, 31069,
515 31079, 31081, 31091, 31121, 31123, 31139, 31147,
516 31151, 31153, 31159, 31177, 31181, 31183, 31189,
517 31193, 31219, 31223, 31231, 31237, 31247, 31249,
518 31253, 31259, 31267, 31271, 31277, 31307, 31319,
519 31321, 31327, 31333, 31337, 31357, 31379, 31387,
520 31391, 31393, 31397, 31469, 31477, 31481, 31489,
521 31511, 31513, 31517, 31531, 31541, 31543, 31547,
522 31567, 31573, 31583, 31601, 31607, 31627, 31643,
523 31649, 31657, 31663, 31667, 31687, 31699, 31721,
524 31723, 31727, 31729, 31741, 31751, 31769, 31771,
525 31793, 31799, 31817, 31847, 31849, 31859, 31873,
526 31883, 31891, 31907, 31957, 31963, 31973, 31981,
527 31991, 32003, 32009, 32027, 32029, 32051, 32057,
528 32059, 32063, 32069, 32077, 32083, 32089, 32099,
529 32117, 32119, 32141, 32143, 32159, 32173, 32183,
530 32189, 32191, 32203, 32213, 32233, 32237, 32251,
531 32257, 32261, 32297, 32299, 32303, 32309, 32321,
532 32323, 32327, 32341, 32353, 32359, 32363, 32369,
533 32371, 32377, 32381, 32401, 32411, 32413, 32423,
534 32429, 32441, 32443, 32467, 32479, 32491, 32497,
535 32503, 32507, 32531, 32533, 32537, 32561, 32563,
536 32569, 32573, 32579, 32587, 32603, 32609, 32611,
537 32621, 32633, 32647, 32653, 32687, 32693, 32707,
538 32713, 32717, 32719, 32749, 32771, 32779, 32783,
539 32789, 32797, 32801, 32803, 32831, 32833, 32839,
540 32843, 32869, 32887, 32909, 32911, 32917, 32933,
541 32939, 32941, 32957, 32969, 32971, 32983, 32987,
542 32993, 32999, 33013, 33023, 33029, 33037, 33049,
543 33053, 33071, 33073, 33083, 33091, 33107, 33113,
544 33119, 33149, 33151, 33161, 33179, 33181, 33191,
545 33199, 33203, 33211, 33223, 33247, 33287, 33289,
546 33301, 33311, 33317, 33329, 33331, 33343, 33347,
547 33349, 33353, 33359, 33377, 33391, 33403, 33409,
548 33413, 33427, 33457, 33461, 33469, 33479, 33487,
549 33493, 33503, 33521, 33529, 33533, 33547, 33563,
550 33569, 33577, 33581, 33587, 33589, 33599, 33601,
551 33613, 33617, 33619, 33623, 33629, 33637, 33641,
552 33647, 33679, 33703, 33713, 33721, 33739, 33749,
553 33751, 33757, 33767, 33769, 33773, 33791, 33797,
554 33809, 33811, 33827, 33829, 33851, 33857, 33863,
555 33871, 33889, 33893, 33911, 33923, 33931, 33937,
556 33941, 33961, 33967, 33997, 34019, 34031, 34033,
557 34039, 34057, 34061, 34123, 34127, 34129, 34141,
558 34147, 34157, 34159, 34171, 34183, 34211, 34213,
559 34217, 34231, 34253, 34259, 34261, 34267, 34273,
560 34283, 34297, 34301, 34303, 34313, 34319, 34327,
561 34337, 34351, 34361, 34367, 34369, 34381, 34403,
562 34421, 34429, 34439, 34457, 34469, 34471, 34483,
563 34487, 34499, 34501, 34511, 34513, 34519, 34537,
564 34543, 34549, 34583, 34589, 34591, 34603, 34607,
565 34613, 34631, 34649, 34651, 34667, 34673, 34679,
566 34687, 34693, 34703, 34721, 34729, 34739, 34747,
567 34757, 34759, 34763, 34781, 34807, 34819, 34841,
568 34843, 34847, 34849, 34871, 34877, 34883, 34897,
569 34913, 34919, 34939, 34949, 34961, 34963, 34981,
570 35023, 35027, 35051, 35053, 35059, 35069, 35081,
571 35083, 35089, 35099, 35107, 35111, 35117, 35129,
572 35141, 35149, 35153, 35159, 35171, 35201, 35221,
573 35227, 35251, 35257, 35267, 35279, 35281, 35291,
574 35311, 35317, 35323, 35327, 35339, 35353, 35363,
575 35381, 35393, 35401, 35407, 35419, 35423, 35437,
576 35447, 35449, 35461, 35491, 35507, 35509, 35521,
577 35527, 35531, 35533, 35537, 35543, 35569, 35573,
578 35591, 35593, 35597, 35603, 35617, 35671, 35677,
579 35729, 35731, 35747, 35753, 35759, 35771, 35797,
580 35801, 35803, 35809, 35831, 35837, 35839, 35851,
581 35863, 35869, 35879, 35897, 35899, 35911, 35923,
582 35933, 35951, 35963, 35969, 35977, 35983, 35993,
583 35999, 36007, 36011, 36013, 36017, 36037, 36061,
584 36067, 36073, 36083, 36097, 36107, 36109, 36131,
585 36137, 36151, 36161, 36187, 36191, 36209, 36217,
586 36229, 36241, 36251, 36263, 36269, 36277, 36293,
587 36299, 36307, 36313, 36319, 36341, 36343, 36353,
588 36373, 36383, 36389, 36433, 36451, 36457, 36467,
589 36469, 36473, 36479, 36493, 36497, 36523, 36527,
590 36529, 36541, 36551, 36559, 36563, 36571, 36583,
591 36587, 36599, 36607, 36629, 36637, 36643, 36653,
592 36671, 36677, 36683, 36691, 36697, 36709, 36713,
593 36721, 36739, 36749, 36761, 36767, 36779, 36781,
594 36787, 36791, 36793, 36809, 36821, 36833, 36847,
595 36857, 36871, 36877, 36887, 36899, 36901, 36913,
596 36919, 36923, 36929, 36931, 36943, 36947, 36973,
597 36979, 36997, 37003, 37013, 37019, 37021, 37039,
598 37049, 37057, 37061, 37087, 37097, 37117, 37123,
599 37139, 37159, 37171, 37181, 37189, 37199, 37201,
600 37217, 37223, 37243, 37253, 37273, 37277, 37307,
601 37309, 37313, 37321, 37337, 37339, 37357, 37361,
602 37363, 37369, 37379, 37397, 37409, 37423, 37441,
603 37447, 37463, 37483, 37489, 37493, 37501, 37507,
604 37511, 37517, 37529, 37537, 37547, 37549, 37561,
605 37567, 37571, 37573, 37579, 37589, 37591, 37607,
606 37619, 37633, 37643, 37649, 37657, 37663, 37691,
607 37693, 37699, 37717, 37747, 37781, 37783, 37799,
608 37811, 37813, 37831, 37847, 37853, 37861, 37871,
609 37879, 37889, 37897, 37907, 37951, 37957, 37963,
610 37967, 37987, 37991, 37993, 37997, 38011, 38039,
611 38047, 38053, 38069, 38083, 38113, 38119, 38149,
612 38153, 38167, 38177, 38183, 38189, 38197, 38201,
613 38219, 38231, 38237, 38239, 38261, 38273, 38281,
614 38287, 38299, 38303, 38317, 38321, 38327, 38329,
615 38333, 38351, 38371, 38377, 38393, 38431, 38447,
616 38449, 38453, 38459, 38461, 38501, 38543, 38557,
617 38561, 38567, 38569, 38593, 38603, 38609, 38611,
618 38629, 38639, 38651, 38653, 38669, 38671, 38677,
619 38693, 38699, 38707, 38711, 38713, 38723, 38729,
620 38737, 38747, 38749, 38767, 38783, 38791, 38803,
621 38821, 38833, 38839, 38851, 38861, 38867, 38873,
622 38891, 38903, 38917, 38921, 38923, 38933, 38953,
623 38959, 38971, 38977, 38993, 39019, 39023, 39041,
624 39043, 39047, 39079, 39089, 39097, 39103, 39107,
625 39113, 39119, 39133, 39139, 39157, 39161, 39163,
626 39181, 39191, 39199, 39209, 39217, 39227, 39229,
627 39233, 39239, 39241, 39251, 39293, 39301, 39313,
628 39317, 39323, 39341, 39343, 39359, 39367, 39371,
629 39373, 39383, 39397, 39409, 39419, 39439, 39443,
630 39451, 39461, 39499, 39503, 39509, 39511, 39521,
631 39541, 39551, 39563, 39569, 39581, 39607, 39619,
632 39623, 39631, 39659, 39667, 39671, 39679, 39703,
633 39709, 39719, 39727, 39733, 39749, 39761, 39769,
634 39779, 39791, 39799, 39821, 39827, 39829, 39839,
635 39841, 39847, 39857, 39863, 39869, 39877, 39883,
636 39887, 39901, 39929, 39937, 39953, 39971, 39979,
637 39983, 39989, 40009, 40013, 40031, 40037, 40039,
638 40063, 40087, 40093, 40099, 40111, 40123, 40127,
639 40129, 40151, 40153, 40163, 40169, 40177, 40189,
640 40193, 40213, 40231, 40237, 40241, 40253, 40277,
641 40283, 40289, 40343, 40351, 40357, 40361, 40387,
642 40423, 40427, 40429, 40433, 40459, 40471, 40483,
643 40487, 40493, 40499, 40507, 40519, 40529, 40531,
644 40543, 40559, 40577, 40583, 40591, 40597, 40609,
645 40627, 40637, 40639, 40693, 40697, 40699, 40709,
646 40739, 40751, 40759, 40763, 40771, 40787, 40801,
647 40813, 40819, 40823, 40829, 40841, 40847, 40849,
648 40853, 40867, 40879, 40883, 40897, 40903, 40927,
649 40933, 40939, 40949, 40961, 40973, 40993, 41011,
650 41017, 41023, 41039, 41047, 41051, 41057, 41077,
651 41081, 41113, 41117, 41131, 41141, 41143, 41149,
652 41161, 41177, 41179, 41183, 41189, 41201, 41203,
653 41213, 41221, 41227, 41231, 41233, 41243, 41257,
654 41263, 41269, 41281, 41299, 41333, 41341, 41351,
655 41357, 41381, 41387, 41389, 41399, 41411, 41413,
656 41443, 41453, 41467, 41479, 41491, 41507, 41513,
657 41519, 41521, 41539, 41543, 41549, 41579, 41593,
658 41597, 41603, 41609, 41611, 41617, 41621, 41627,
659 41641, 41647, 41651, 41659, 41669, 41681, 41687,
660 41719, 41729, 41737, 41759, 41761, 41771, 41777,
661 41801, 41809, 41813, 41843, 41849, 41851, 41863,
662 41879, 41887, 41893, 41897, 41903, 41911, 41927,
663 41941, 41947, 41953, 41957, 41959, 41969, 41981,
664 41983, 41999, 42013, 42017, 42019, 42023, 42043,
665 42061, 42071, 42073, 42083, 42089, 42101, 42131,
666 42139, 42157, 42169, 42179, 42181, 42187, 42193,
667 42197, 42209, 42221, 42223, 42227, 42239, 42257,
668 42281, 42283, 42293, 42299, 42307, 42323, 42331,
669 42337, 42349, 42359, 42373, 42379, 42391, 42397,
670 42403, 42407, 42409, 42433, 42437, 42443, 42451,
671 42457, 42461, 42463, 42467, 42473, 42487, 42491,
672 42499, 42509, 42533, 42557, 42569, 42571, 42577,
673 42589, 42611, 42641, 42643, 42649, 42667, 42677,
674 42683, 42689, 42697, 42701, 42703, 42709, 42719,
675 42727, 42737, 42743, 42751, 42767, 42773, 42787,
676 42793, 42797, 42821, 42829, 42839, 42841, 42853,
677 42859, 42863, 42899, 42901, 42923, 42929, 42937,
678 42943, 42953, 42961, 42967, 42979, 42989, 43003,
679 43013, 43019, 43037, 43049, 43051, 43063, 43067,
680 43093, 43103, 43117, 43133, 43151, 43159, 43177,
681 43189, 43201, 43207, 43223, 43237, 43261, 43271,
682 43283, 43291, 43313, 43319, 43321, 43331, 43391,
683 43397, 43399, 43403, 43411, 43427, 43441, 43451,
684 43457, 43481, 43487, 43499, 43517, 43541, 43543,
685 43573, 43577, 43579, 43591, 43597, 43607, 43609,
686 43613, 43627, 43633, 43649, 43651, 43661, 43669,
687 43691, 43711, 43717, 43721, 43753, 43759, 43777,
688 43781, 43783, 43787, 43789, 43793, 43801, 43853,
689 43867, 43889, 43891, 43913, 43933, 43943, 43951,
690 43961, 43963, 43969, 43973, 43987, 43991, 43997,
691 44017, 44021, 44027, 44029, 44041, 44053, 44059,
692 44071, 44087, 44089, 44101, 44111, 44119, 44123,
693 44129, 44131, 44159, 44171, 44179, 44189, 44201,
694 44203, 44207, 44221, 44249, 44257, 44263, 44267,
695 44269, 44273, 44279, 44281, 44293, 44351, 44357,
696 44371, 44381, 44383, 44389, 44417, 44449, 44453,
697 44483, 44491, 44497, 44501, 44507, 44519, 44531,
698 44533, 44537, 44543, 44549, 44563, 44579, 44587,
699 44617, 44621, 44623, 44633, 44641, 44647, 44651,
700 44657, 44683, 44687, 44699, 44701, 44711, 44729,
701 44741, 44753, 44771, 44773, 44777, 44789, 44797,
702 44809, 44819, 44839, 44843, 44851, 44867, 44879,
703 44887, 44893, 44909, 44917, 44927, 44939, 44953,
704 44959, 44963, 44971, 44983, 44987, 45007, 45013,
705 45053, 45061, 45077, 45083, 45119, 45121, 45127,
706 45131, 45137, 45139, 45161, 45179, 45181, 45191,
707 45197, 45233, 45247, 45259, 45263, 45281, 45289,
708 45293, 45307, 45317, 45319, 45329, 45337, 45341,
709 45343, 45361, 45377, 45389, 45403, 45413, 45427,
710 45433, 45439, 45481, 45491, 45497, 45503, 45523,
711 45533, 45541, 45553, 45557, 45569, 45587, 45589,
712 45599, 45613, 45631, 45641, 45659, 45667, 45673,
713 45677, 45691, 45697, 45707, 45737, 45751, 45757,
714 45763, 45767, 45779, 45817, 45821, 45823, 45827,
715 45833, 45841, 45853, 45863, 45869, 45887, 45893,
716 45943, 45949, 45953, 45959, 45971, 45979, 45989,
717 46021, 46027, 46049, 46051, 46061, 46073, 46091,
718 46093, 46099, 46103, 46133, 46141, 46147, 46153,
719 46171, 46181, 46183, 46187, 46199, 46219, 46229,
720 46237, 46261, 46271, 46273, 46279, 46301, 46307,
721 46309, 46327, 46337, 46349, 46351, 46381, 46399,
722 46411, 46439, 46441, 46447, 46451, 46457, 46471,
723 46477, 46489, 46499, 46507, 46511, 46523, 46549,
724 46559, 46567, 46573, 46589, 46591, 46601, 46619,
725 46633, 46639, 46643, 46649, 46663, 46679, 46681,
726 46687, 46691, 46703, 46723, 46727, 46747, 46751,
727 46757, 46769, 46771, 46807, 46811, 46817, 46819,
728 46829, 46831, 46853, 46861, 46867, 46877, 46889,
729 46901, 46919, 46933, 46957, 46993, 46997, 47017,
730 47041, 47051, 47057, 47059, 47087, 47093, 47111,
731 47119, 47123, 47129, 47137, 47143, 47147, 47149,
732 47161, 47189, 47207, 47221, 47237, 47251, 47269,
733 47279, 47287, 47293, 47297, 47303, 47309, 47317,
734 47339, 47351, 47353, 47363, 47381, 47387, 47389,
735 47407, 47417, 47419, 47431, 47441, 47459, 47491,
736 47497, 47501, 47507, 47513, 47521, 47527, 47533,
737 47543, 47563, 47569, 47581, 47591, 47599, 47609,
738 47623, 47629, 47639, 47653, 47657, 47659, 47681,
739 47699, 47701, 47711, 47713, 47717, 47737, 47741,
740 47743, 47777, 47779, 47791, 47797, 47807, 47809,
741 47819, 47837, 47843, 47857, 47869, 47881, 47903,
742 47911, 47917, 47933, 47939, 47947, 47951, 47963,
743 47969, 47977, 47981, 48017, 48023, 48029, 48049,
744 48073, 48079, 48091, 48109, 48119, 48121, 48131,
745 48157, 48163, 48179, 48187, 48193, 48197, 48221,
746 48239, 48247, 48259, 48271, 48281, 48299, 48311,
747 48313, 48337, 48341, 48353, 48371, 48383, 48397,
748 48407, 48409, 48413, 48437, 48449, 48463, 48473,
749 48479, 48481, 48487, 48491, 48497, 48523, 48527,
750 48533, 48539, 48541, 48563, 48571, 48589, 48593,
751 48611, 48619, 48623, 48647, 48649, 48661, 48673,
752 48677, 48679, 48731, 48733, 48751, 48757, 48761,
753 48767, 48779, 48781, 48787, 48799, 48809, 48817,
754 48821, 48823, 48847, 48857, 48859, 48869, 48871,
755 48883, 48889, 48907, 48947, 48953, 48973, 48989,
756 48991, 49003, 49009, 49019, 49031, 49033, 49037,
757 49043, 49057, 49069, 49081, 49103, 49109, 49117,
758 49121, 49123, 49139, 49157, 49169, 49171, 49177,
759 49193, 49199, 49201, 49207, 49211, 49223, 49253,
760 49261, 49277, 49279, 49297, 49307, 49331, 49333,
761 49339, 49363, 49367, 49369, 49391, 49393, 49409,
762 49411, 49417, 49429, 49433, 49451, 49459, 49463,
763 49477, 49481, 49499, 49523, 49529, 49531, 49537,
764 49547, 49549, 49559, 49597, 49603, 49613, 49627,
765 49633, 49639, 49663, 49667, 49669, 49681, 49697,
766 49711, 49727, 49739, 49741, 49747, 49757, 49783,
767 49787, 49789, 49801, 49807, 49811, 49823, 49831,
768 49843, 49853, 49871, 49877, 49891, 49919, 49921,
769 49927, 49937, 49939, 49943, 49957, 49991, 49993,
770 49999, 50021, 50023, 50033, 50047, 50051, 50053,
771 50069, 50077, 50087, 50093, 50101, 50111, 50119,
772 50123, 50129, 50131, 50147, 50153, 50159, 50177,
773 50207, 50221, 50227, 50231, 50261, 50263, 50273,
774 50287, 50291, 50311, 50321, 50329, 50333, 50341,
775 50359, 50363, 50377, 50383, 50387, 50411, 50417,
776 50423, 50441, 50459, 50461, 50497, 50503, 50513,
777 50527, 50539, 50543, 50549, 50551, 50581, 50587,
778 50591, 50593, 50599, 50627, 50647, 50651, 50671,
779 50683, 50707, 50723, 50741, 50753, 50767, 50773,
780 50777, 50789, 50821, 50833, 50839, 50849, 50857,
781 50867, 50873, 50891, 50893, 50909, 50923, 50929,
782 50951, 50957, 50969, 50971, 50989, 50993, 51001,
783 51031, 51043, 51047, 51059, 51061, 51071, 51109,
784 51131, 51133, 51137, 51151, 51157, 51169, 51193,
785 51197, 51199, 51203, 51217, 51229, 51239, 51241,
786 51257, 51263, 51283, 51287, 51307, 51329, 51341,
787 51343, 51347, 51349, 51361, 51383, 51407, 51413,
788 51419, 51421, 51427, 51431, 51437, 51439, 51449,
789 51461, 51473, 51479, 51481, 51487, 51503, 51511,
790 51517, 51521, 51539, 51551, 51563, 51577, 51581,
791 51593, 51599, 51607, 51613, 51631, 51637, 51647,
792 51659, 51673, 51679, 51683, 51691, 51713, 51719,
793 51721, 51749, 51767, 51769, 51787, 51797, 51803,
794 51817, 51827, 51829, 51839, 51853, 51859, 51869,
795 51871, 51893, 51899, 51907, 51913, 51929, 51941,
796 51949, 51971, 51973, 51977, 51991, 52009, 52021,
797 52027, 52051, 52057, 52067, 52069, 52081, 52103,
798 52121, 52127, 52147, 52153, 52163, 52177, 52181,
799 52183, 52189, 52201, 52223, 52237, 52249, 52253,
800 52259, 52267, 52289, 52291, 52301, 52313, 52321,
801 52361, 52363, 52369, 52379, 52387, 52391, 52433,
802 52453, 52457, 52489, 52501, 52511, 52517, 52529,
803 52541, 52543, 52553, 52561, 52567, 52571, 52579,
804 52583, 52609, 52627, 52631, 52639, 52667, 52673,
805 52691, 52697, 52709, 52711, 52721, 52727, 52733,
806 52747, 52757, 52769, 52783, 52807, 52813, 52817,
807 52837, 52859, 52861, 52879, 52883, 52889, 52901,
808 52903, 52919, 52937, 52951, 52957, 52963, 52967,
809 52973, 52981, 52999, 53003, 53017, 53047, 53051,
810 53069, 53077, 53087, 53089, 53093, 53101, 53113,
811 53117, 53129, 53147, 53149, 53161, 53171, 53173,
812 53189, 53197, 53201, 53231, 53233, 53239, 53267,
813 53269, 53279, 53281, 53299, 53309, 53323, 53327,
814 53353, 53359, 53377, 53381, 53401, 53407, 53411,
815 53419, 53437, 53441, 53453, 53479, 53503, 53507,
816 53527, 53549, 53551, 53569, 53591, 53593, 53597,
817 53609, 53611, 53617, 53623, 53629, 53633, 53639,
818 53653, 53657, 53681, 53693, 53699, 53717, 53719,
819 53731, 53759, 53773, 53777, 53783, 53791, 53813,
820 53819, 53831, 53849, 53857, 53861, 53881, 53887,
821 53891, 53897, 53899, 53917, 53923, 53927, 53939,
822 53951, 53959, 53987, 53993, 54001, 54011, 54013,
823 54037, 54049, 54059, 54083, 54091, 54101, 54121,
824 54133, 54139, 54151, 54163, 54167, 54181, 54193,
825 54217, 54251, 54269, 54277, 54287, 54293, 54311,
826 54319, 54323, 54331, 54347, 54361, 54367, 54371,
827 54377, 54401, 54403, 54409, 54413, 54419, 54421,
828 54437, 54443, 54449, 54469, 54493, 54497, 54499,
829 54503, 54517, 54521, 54539, 54541, 54547, 54559,
830 54563, 54577, 54581, 54583, 54601, 54617, 54623,
831 54629, 54631, 54647, 54667, 54673, 54679, 54709,
832 54713, 54721, 54727, 54751, 54767, 54773, 54779,
833 54787, 54799, 54829, 54833, 54851, 54869, 54877,
834 54881, 54907, 54917, 54919, 54941, 54949, 54959,
835 54973, 54979, 54983, 55001, 55009, 55021, 55049,
836 55051, 55057, 55061, 55073, 55079, 55103, 55109,
837 55117, 55127, 55147, 55163, 55171, 55201, 55207,
838 55213, 55217, 55219, 55229, 55243, 55249, 55259,
839 55291, 55313, 55331, 55333, 55337, 55339, 55343,
840 55351, 55373, 55381, 55399, 55411, 55439, 55441,
841 55457, 55469, 55487, 55501, 55511, 55529, 55541,
842 55547, 55579, 55589, 55603, 55609, 55619, 55621,
843 55631, 55633, 55639, 55661, 55663, 55667, 55673,
844 55681, 55691, 55697, 55711, 55717, 55721, 55733,
845 55763, 55787, 55793, 55799, 55807, 55813, 55817,
846 55819, 55823, 55829, 55837, 55843, 55849, 55871,
847 55889, 55897, 55901, 55903, 55921, 55927, 55931,
848 55933, 55949, 55967, 55987, 55997, 56003, 56009,
849 56039, 56041, 56053, 56081, 56087, 56093, 56099,
850 56101, 56113, 56123, 56131, 56149, 56167, 56171,
851 56179, 56197, 56207, 56209, 56237, 56239, 56249,
852 56263, 56267, 56269, 56299, 56311, 56333, 56359,
853 56369, 56377, 56383, 56393, 56401, 56417, 56431,
854 56437, 56443, 56453, 56467, 56473, 56477, 56479,
855 56489, 56501, 56503, 56509, 56519, 56527, 56531,
856 56533, 56543, 56569, 56591, 56597, 56599, 56611,
857 56629, 56633, 56659, 56663, 56671, 56681, 56687,
858 56701, 56711, 56713, 56731, 56737, 56747, 56767,
859 56773, 56779, 56783, 56807, 56809, 56813, 56821,
860 56827, 56843, 56857, 56873, 56891, 56893, 56897,
861 56909, 56911, 56921, 56923, 56929, 56941, 56951,
862 56957, 56963, 56983, 56989, 56993, 56999, 57037,
863 57041, 57047, 57059, 57073, 57077, 57089, 57097,
864 57107, 57119, 57131, 57139, 57143, 57149, 57163,
865 57173, 57179, 57191, 57193, 57203, 57221, 57223,
866 57241, 57251, 57259, 57269, 57271, 57283, 57287,
867 57301, 57329, 57331, 57347, 57349, 57367, 57373,
868 57383, 57389, 57397, 57413, 57427, 57457, 57467,
869 57487, 57493, 57503, 57527, 57529, 57557, 57559,
870 57571, 57587, 57593, 57601, 57637, 57641, 57649,
871 57653, 57667, 57679, 57689, 57697, 57709, 57713,
872 57719, 57727, 57731, 57737, 57751, 57773, 57781,
873 57787, 57791, 57793, 57803, 57809, 57829, 57839,
874 57847, 57853, 57859, 57881, 57899, 57901, 57917,
875 57923, 57943, 57947, 57973, 57977, 57991, 58013,
876 58027, 58031, 58043, 58049, 58057, 58061, 58067,
877 58073, 58099, 58109, 58111, 58129, 58147, 58151,
878 58153, 58169, 58171, 58189, 58193, 58199, 58207,
879 58211, 58217, 58229, 58231, 58237, 58243, 58271,
880 58309, 58313, 58321, 58337, 58363, 58367, 58369,
881 58379, 58391, 58393, 58403, 58411, 58417, 58427,
882 58439, 58441, 58451, 58453, 58477, 58481, 58511,
883 58537, 58543, 58549, 58567, 58573, 58579, 58601,
884 58603, 58613, 58631, 58657, 58661, 58679, 58687,
885 58693, 58699, 58711, 58727, 58733, 58741, 58757,
886 58763, 58771, 58787, 58789, 58831, 58889, 58897,
887 58901, 58907, 58909, 58913, 58921, 58937, 58943,
888 58963, 58967, 58979, 58991, 58997, 59009, 59011,
889 59021, 59023, 59029, 59051, 59053, 59063, 59069,
890 59077, 59083, 59093, 59107, 59113, 59119, 59123,
891 59141, 59149, 59159, 59167, 59183, 59197, 59207,
892 59209, 59219, 59221, 59233, 59239, 59243, 59263,
893 59273, 59281, 59333, 59341, 59351, 59357, 59359,
894 59369, 59377, 59387, 59393, 59399, 59407, 59417,
895 59419, 59441, 59443, 59447, 59453, 59467, 59471,
896 59473, 59497, 59509, 59513, 59539, 59557, 59561,
897 59567, 59581, 59611, 59617, 59621, 59627, 59629,
898 59651, 59659, 59663, 59669, 59671, 59693, 59699,
899 59707, 59723, 59729, 59743, 59747, 59753, 59771,
900 59779, 59791, 59797, 59809, 59833, 59863, 59879,
901 59887, 59921, 59929, 59951, 59957, 59971, 59981,
902 59999, 60013, 60017, 60029, 60037, 60041, 60077,
903 60083, 60089, 60091, 60101, 60103, 60107, 60127,
904 60133, 60139, 60149, 60161, 60167, 60169, 60209,
905 60217, 60223, 60251, 60257, 60259, 60271, 60289,
906 60293, 60317, 60331, 60337, 60343, 60353, 60373,
907 60383, 60397, 60413, 60427, 60443, 60449, 60457,
908 60493, 60497, 60509, 60521, 60527, 60539, 60589,
909 60601, 60607, 60611, 60617, 60623, 60631, 60637,
910 60647, 60649, 60659, 60661, 60679, 60689, 60703,
911 60719, 60727, 60733, 60737, 60757, 60761, 60763,
912 60773, 60779, 60793, 60811, 60821, 60859, 60869,
913 60887, 60889, 60899, 60901, 60913, 60917, 60919,
914 60923, 60937, 60943, 60953, 60961, 61001, 61007,
915 61027, 61031, 61043, 61051, 61057, 61091, 61099,
916 61121, 61129, 61141, 61151, 61153, 61169, 61211,
917 61223, 61231, 61253, 61261, 61283, 61291, 61297,
918 61331, 61333, 61339, 61343, 61357, 61363, 61379,
919 61381, 61403, 61409, 61417, 61441, 61463, 61469,
920 61471, 61483, 61487, 61493, 61507, 61511, 61519,
921 61543, 61547, 61553, 61559, 61561, 61583, 61603,
922 61609, 61613, 61627, 61631, 61637, 61643, 61651,
923 61657, 61667, 61673, 61681, 61687, 61703, 61717,
924 61723, 61729, 61751, 61757, 61781, 61813, 61819,
925 61837, 61843, 61861, 61871, 61879, 61909, 61927,
926 61933, 61949, 61961, 61967, 61979, 61981, 61987,
927 61991, 62003, 62011, 62017, 62039, 62047, 62053,
928 62057, 62071, 62081, 62099, 62119, 62129, 62131,
929 62137, 62141, 62143, 62171, 62189, 62191, 62201,
930 62207, 62213, 62219, 62233, 62273, 62297, 62299,
931 62303, 62311, 62323, 62327, 62347, 62351, 62383,
932 62401, 62417, 62423, 62459, 62467, 62473, 62477,
933 62483, 62497, 62501, 62507, 62533, 62539, 62549,
934 62563, 62581, 62591, 62597, 62603, 62617, 62627,
935 62633, 62639, 62653, 62659, 62683, 62687, 62701,
936 62723, 62731, 62743, 62753, 62761, 62773, 62791,
937 62801, 62819, 62827, 62851, 62861, 62869, 62873,
938 62897, 62903, 62921, 62927, 62929, 62939, 62969,
939 62971, 62981, 62983, 62987, 62989, 63029, 63031,
940 63059, 63067, 63073, 63079, 63097, 63103, 63113,
941 63127, 63131, 63149, 63179, 63197, 63199, 63211,
942 63241, 63247, 63277, 63281, 63299, 63311, 63313,
943 63317, 63331, 63337, 63347, 63353, 63361, 63367,
944 63377, 63389, 63391, 63397, 63409, 63419, 63421,
945 63439, 63443, 63463, 63467, 63473, 63487, 63493,
946 63499, 63521, 63527, 63533, 63541, 63559, 63577,
947 63587, 63589, 63599, 63601, 63607, 63611, 63617,
948 63629, 63647, 63649, 63659, 63667, 63671, 63689,
949 63691, 63697, 63703, 63709, 63719, 63727, 63737,
950 63743, 63761, 63773, 63781, 63793, 63799, 63803,
951 63809, 63823, 63839, 63841, 63853, 63857, 63863,
952 63901, 63907, 63913, 63929, 63949, 63977, 63997,
953 64007, 64013, 64019, 64033, 64037, 64063, 64067,
954 64081, 64091, 64109, 64123, 64151, 64153, 64157,
955 64171, 64187, 64189, 64217, 64223, 64231, 64237,
956 64271, 64279, 64283, 64301, 64303, 64319, 64327,
957 64333, 64373, 64381, 64399, 64403, 64433, 64439,
958 64451, 64453, 64483, 64489, 64499, 64513, 64553,
959 64567, 64577, 64579, 64591, 64601, 64609, 64613,
960 64621, 64627, 64633, 64661, 64663, 64667, 64679,
961 64693, 64709, 64717, 64747, 64763, 64781, 64783,
962 64793, 64811, 64817, 64849, 64853, 64871, 64877,
963 64879, 64891, 64901, 64919, 64921, 64927, 64937,
964 64951, 64969, 64997, 65003, 65011, 65027, 65029,
965 65033, 65053, 65063, 65071, 65089, 65099, 65101,
966 65111, 65119, 65123, 65129, 65141, 65147, 65167,
967 65171, 65173, 65179, 65183, 65203, 65213, 65239,
968 65257, 65267, 65269, 65287, 65293, 65309, 65323,
969 65327, 65353, 65357, 65371, 65381, 65393, 65407,
970 65413, 65419, 65423, 65437, 65447, 65449, 65479,
971 65497, 65519, 65521, 0
972 };
973
974 /* Tests if the (small) number provided is a prime.
975 */
small_prime_check(unsigned x)976 static unsigned small_prime_check(unsigned x)
977 {
978 unsigned j, t, square, prime;
979
980 for (j = 0; primes[j] > 0; j++) {
981 prime = primes[j];
982 square = prime * prime;
983
984 if (square > x)
985 break;
986
987 t = x / prime;
988 if (t * prime == x)
989 return 0;
990 }
991
992 return 1;
993 }
994
995 /* The seed in FIPS186-3 is used either as an integer or blob,
996 * but when used as an integer it must not be trunacated below
997 * the "nominal" seed size. This function returns the size
998 * that way. */
mpz_seed_sizeinbase_256_u(mpz_t s,unsigned nominal)999 unsigned mpz_seed_sizeinbase_256_u(mpz_t s, unsigned nominal)
1000 {
1001 unsigned ret = nettle_mpz_sizeinbase_256_u(s);
1002 if (ret < nominal)
1003 return nominal;
1004 return ret;
1005 }
1006
st_provable_prime_small(mpz_t p,unsigned * prime_seed_length,void * prime_seed,unsigned * prime_gen_counter,unsigned bits,unsigned seed_length,const void * seed,void * progress_ctx,nettle_progress_func * progress)1007 static int st_provable_prime_small(mpz_t p,
1008 unsigned *prime_seed_length,
1009 void *prime_seed,
1010 unsigned *prime_gen_counter, unsigned bits,
1011 unsigned seed_length, const void *seed,
1012 void *progress_ctx,
1013 nettle_progress_func * progress)
1014 {
1015 unsigned gen_counter = 0;
1016 unsigned tseed_length;
1017 uint8_t tseed[MAX_PVP_SEED_SIZE+1];
1018 uint8_t h1[DIGEST_SIZE];
1019 uint8_t h2[DIGEST_SIZE];
1020 uint32_t c;
1021 mpz_t s;
1022 unsigned highbit;
1023
1024 assert(bits >= 2 && bits <= 32);
1025
1026 mpz_init(s);
1027
1028 /* seed is handled as mpz_t instead of simply using INCREMENT
1029 * for the few (unlikely) cases where seed overflows. */
1030 nettle_mpz_set_str_256_u(s, seed_length, seed);
1031
1032 retry:
1033 tseed_length = mpz_seed_sizeinbase_256_u(s, seed_length);
1034 if (tseed_length > sizeof(tseed)) {
1035 goto fail;
1036 }
1037
1038 /* c = Hash(seed) XOR Hash(seed+1) */
1039 nettle_mpz_get_str_256(tseed_length, tseed, s);
1040
1041 hash(h1, tseed_length, tseed);
1042
1043 mpz_add_ui(s, s, 1);
1044
1045 tseed_length = mpz_seed_sizeinbase_256_u(s, seed_length);
1046 if (tseed_length > sizeof(tseed))
1047 goto fail;
1048
1049 nettle_mpz_get_str_256(tseed_length, tseed, s);
1050
1051 hash(h2, tseed_length, tseed);
1052
1053 memxor(h1, h2, DIGEST_SIZE);
1054
1055 /* c = 2^(bits-1) + (c mod 2^(bits-1)) */
1056 highbit = 1L << (bits - 1);
1057
1058 c = READ_UINT32(&h1[DIGEST_SIZE - 4]);
1059
1060 c &= highbit - 1;
1061
1062 /* Make sure c is odd and high bit is set */
1063 c |= highbit | 1;
1064
1065 gen_counter++;
1066
1067 /* seed++ */
1068 mpz_add_ui(s, s, 1);
1069
1070 /* deterministic primality check on c */
1071 if (small_prime_check(c) == 0) {
1072 /* not a prime */
1073 if (gen_counter >= 4 * bits)
1074 goto fail; /* failed */
1075
1076 if (progress)
1077 progress(progress_ctx, 'x');
1078
1079 goto retry;
1080 }
1081
1082 /* success */
1083 mpz_set_ui(p, c);
1084
1085 if (prime_seed != NULL) {
1086 tseed_length = mpz_seed_sizeinbase_256_u(s, tseed_length);
1087 if (*prime_seed_length < tseed_length)
1088 goto fail;
1089
1090 nettle_mpz_get_str_256(tseed_length, prime_seed, s);
1091 *prime_seed_length = tseed_length;
1092 }
1093
1094 if (prime_gen_counter)
1095 *prime_gen_counter = gen_counter;
1096
1097 mpz_clear(s);
1098 return 1;
1099
1100 fail:
1101 mpz_clear(s);
1102 return 0;
1103 }
1104
1105 /* The Shawe-Taylor algorithm described in FIPS 186-4.
1106 *
1107 * p: (output) the prime
1108 * prime_seed_length: (output) the length of prime_seed. Initially
1109 * must hold the maximum size of prime_seed. The size should be a
1110 * byte more than seed_length.
1111 * prime_seed: (output) the prime_seed (may be NULL)
1112 * prime_gen_counter: A counter determined during the prime generation
1113 * bits: The requested number of bits for prime
1114 * seed_length: The length of seed. It is limited by MAX_PVP_SEED_SIZE.
1115 * seed: The initial seed
1116 *
1117 * Returns non zero on success.
1118 */
1119 int
st_provable_prime(mpz_t p,unsigned * prime_seed_length,void * prime_seed,unsigned * prime_gen_counter,unsigned bits,unsigned seed_length,const void * seed,void * progress_ctx,nettle_progress_func * progress)1120 st_provable_prime(mpz_t p,
1121 unsigned *prime_seed_length, void *prime_seed,
1122 unsigned *prime_gen_counter,
1123 unsigned bits,
1124 unsigned seed_length, const void *seed,
1125 void *progress_ctx, nettle_progress_func * progress)
1126 {
1127 unsigned gen_counter;
1128 unsigned tseed_length;
1129 uint8_t tseed[MAX_PVP_SEED_SIZE+1];
1130 int ret;
1131 unsigned pseed_length, iterations;
1132 uint8_t *pseed;
1133 unsigned old_counter, i;
1134 mpz_t s, tmp, r, dc0, c0, c, t, z;
1135 uint8_t *storage = NULL;
1136 unsigned storage_length = 0;
1137
1138 if (bits < 33) {
1139 return st_provable_prime_small(p, prime_seed_length, prime_seed,
1140 prime_gen_counter, bits,
1141 seed_length, seed, progress_ctx,
1142 progress);
1143 }
1144
1145 mpz_init(s);
1146 mpz_init(tmp);
1147 mpz_init(r);
1148 mpz_init(c);
1149 mpz_init(z);
1150 mpz_init(t);
1151 mpz_init(c0);
1152 mpz_init(dc0);
1153
1154 pseed_length = seed_length + 2;
1155
1156 pseed = gnutls_malloc(pseed_length);
1157 if (pseed == NULL)
1158 goto fail;
1159
1160 ret = st_provable_prime(c0, &pseed_length, pseed, &gen_counter,
1161 1+div_ceil(bits, 2), seed_length, seed,
1162 progress_ctx, progress);
1163 if (ret == 0)
1164 goto fail;
1165
1166 nettle_mpz_set_str_256_u(s, pseed_length, pseed);
1167
1168 /* the spec says to remove 1 here */
1169 iterations = div_ceil(bits, DIGEST_SIZE * 8);
1170 old_counter = gen_counter;
1171
1172 mpz_set_ui(tmp, 0); /* x = 0 */
1173 if (iterations > 0) {
1174 storage_length = iterations * DIGEST_SIZE;
1175
1176 storage = malloc(storage_length);
1177 if (storage == NULL)
1178 goto fail;
1179
1180 for (i = 0; i < iterations; i++) {
1181 tseed_length = mpz_seed_sizeinbase_256_u(s, pseed_length);
1182 if (tseed_length > sizeof(tseed))
1183 goto fail;
1184 nettle_mpz_get_str_256(tseed_length, tseed, s);
1185
1186 hash(&storage
1187 [(iterations - i - 1) * DIGEST_SIZE],
1188 tseed_length, tseed);
1189 mpz_add_ui(s, s, 1);
1190 }
1191
1192 nettle_mpz_set_str_256_u(tmp, storage_length, storage);
1193 }
1194
1195 /* tmp = 2^(bits-1) + (tmp mod 2^(bits-1)) */
1196 mpz_set_ui(r, 1);
1197 mpz_mul_2exp(r, r, bits - 1); /* r = 2^(bits-1) */
1198
1199 mpz_fdiv_r_2exp(tmp, tmp, bits - 1);
1200 mpz_add(tmp, tmp, r); /* tmp = x */
1201
1202 /* Generate candidate prime c in [2^(bits-1), 2^bits] */
1203
1204 /* t = u[x/2c0] */
1205 mpz_mul_2exp(dc0, c0, 1); /* dc0 = 2*c0 */
1206 mpz_cdiv_q(t, tmp, dc0);
1207
1208 retry:
1209 /* c = t*(2c0) + 1 */
1210 mpz_mul(c, dc0, t);
1211 mpz_add_ui(c, c, 1);
1212
1213 mpz_set_ui(r, 1);
1214 mpz_mul_2exp(r, r, bits); /* r = 2^(bits) */
1215
1216 /* if 2tc0+1 > 2^bits */
1217 if (mpz_cmp(c, r) > 0) {
1218 /* t = 2^(bits-1)/2c0 */
1219
1220 mpz_fdiv_q_2exp(r, r, 1); /* r = 2^(bits-1) */
1221 mpz_cdiv_q(t, r, dc0);
1222
1223 /* c = t* 2c0 + 1 */
1224 mpz_mul(c, dc0, t);
1225 mpz_add_ui(c, c, 1);
1226 }
1227
1228 gen_counter++;
1229
1230 mpz_set_ui(r, 0); /* a = 0 */
1231 if (iterations > 0) {
1232 for (i = 0; i < iterations; i++) {
1233 tseed_length = mpz_seed_sizeinbase_256_u(s, pseed_length);
1234 if (tseed_length > sizeof(tseed))
1235 goto fail;
1236
1237 nettle_mpz_get_str_256(tseed_length, tseed, s);
1238
1239 hash(&storage
1240 [(iterations - i - 1) * DIGEST_SIZE],
1241 tseed_length, tseed);
1242 mpz_add_ui(s, s, 1);
1243 }
1244
1245 /* r = a */
1246 nettle_mpz_set_str_256_u(r, storage_length, storage);
1247 }
1248
1249 /* a = 2 + (a mod (c-3)) */
1250 mpz_sub_ui(tmp, c, 3); /* c is too large to worry about negatives */
1251 mpz_mod(r, r, tmp);
1252 mpz_add_ui(r, r, 2);
1253
1254 /* z = a^(2t) mod c */
1255 mpz_mul_2exp(tmp, t, 1); /* tmp = 2t */
1256 mpz_powm(z, r, tmp, c);
1257
1258 mpz_sub_ui(tmp, z, 1);
1259
1260 mpz_gcd(r, tmp, c);
1261
1262 if (mpz_cmp_ui(r, 1) == 0) {
1263 mpz_powm(tmp, z, c0, c);
1264 if (mpz_cmp_ui(tmp, 1) == 0) {
1265 mpz_set(p, c);
1266
1267 if (prime_seed != NULL) {
1268 tseed_length = mpz_seed_sizeinbase_256_u(s, pseed_length);
1269 if (*prime_seed_length < tseed_length)
1270 goto fail;
1271
1272 nettle_mpz_get_str_256(tseed_length,
1273 prime_seed, s);
1274 *prime_seed_length = tseed_length;
1275 }
1276
1277 if (prime_gen_counter)
1278 *prime_gen_counter = gen_counter;
1279
1280 goto success;
1281 }
1282 }
1283
1284 if (progress)
1285 progress(progress_ctx, 'x');
1286
1287 if (gen_counter >= (4 * bits + old_counter)) {
1288 goto fail;
1289 }
1290
1291 mpz_add_ui(t, t, 1);
1292 goto retry;
1293
1294 success:
1295 ret = 1;
1296 goto finish;
1297
1298 fail:
1299 ret = 0;
1300
1301 finish:
1302 mpz_clear(c0);
1303 mpz_clear(dc0);
1304 mpz_clear(r);
1305 mpz_clear(s);
1306 mpz_clear(z);
1307 mpz_clear(t);
1308 mpz_clear(tmp);
1309 mpz_clear(c);
1310 free(pseed);
1311 free(storage);
1312 return ret;
1313 }
1314