/src/gnutls/lib/nettle/int/provable-prime.c

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

Coverage Report

Created: 2023-03-26 08:33