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

Coverage Report

Created: 2025-03-18 06:55