2 * Copyright 1998-2016 The OpenSSL Project Authors. All Rights Reserved.
4 * Licensed under the OpenSSL license (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
10 typedef unsigned short prime_t;
11 # define NUMPRIMES 2048
13 static const prime_t primes[2048] = {
15 2, 3, 5, 7, 11, 13, 17, 19,
16 23, 29, 31, 37, 41, 43, 47, 53,
17 59, 61, 67, 71, 73, 79, 83, 89,
18 97, 101, 103, 107, 109, 113, 127, 131,
19 137, 139, 149, 151, 157, 163, 167, 173,
20 179, 181, 191, 193, 197, 199, 211, 223,
21 227, 229, 233, 239, 241, 251, 257, 263,
22 269, 271, 277, 281, 283, 293, 307, 311,
23 313, 317, 331, 337, 347, 349, 353, 359,
24 367, 373, 379, 383, 389, 397, 401, 409,
25 419, 421, 431, 433, 439, 443, 449, 457,
26 461, 463, 467, 479, 487, 491, 499, 503,
27 509, 521, 523, 541, 547, 557, 563, 569,
28 571, 577, 587, 593, 599, 601, 607, 613,
29 617, 619, 631, 641, 643, 647, 653, 659,
30 661, 673, 677, 683, 691, 701, 709, 719,
31 727, 733, 739, 743, 751, 757, 761, 769,
32 773, 787, 797, 809, 811, 821, 823, 827,
33 829, 839, 853, 857, 859, 863, 877, 881,
34 883, 887, 907, 911, 919, 929, 937, 941,
35 947, 953, 967, 971, 977, 983, 991, 997,
36 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049,
37 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097,
38 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163,
39 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
40 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283,
41 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321,
42 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423,
43 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459,
44 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
45 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571,
46 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619,
47 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693,
48 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747,
49 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
50 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877,
51 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949,
52 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003,
53 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069,
54 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,
55 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203,
56 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267,
57 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311,
58 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377,
59 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
60 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503,
61 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579,
62 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657,
63 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693,
64 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
65 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801,
66 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861,
67 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939,
68 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011,
69 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
70 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167,
71 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221,
72 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301,
73 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347,
74 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
75 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491,
76 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541,
77 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607,
78 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671,
79 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727,
80 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797,
81 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863,
82 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923,
83 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003,
84 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057,
85 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129,
86 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211,
87 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259,
88 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337,
89 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,
90 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481,
91 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547,
92 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621,
93 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673,
94 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751,
95 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813,
96 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909,
97 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967,
98 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011,
99 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087,
100 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167,
101 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233,
102 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309,
103 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399,
104 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443,
105 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507,
106 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573,
107 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653,
108 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711,
109 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791,
110 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849,
111 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897,
112 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007,
113 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073,
114 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133,
115 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211,
116 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271,
117 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329,
118 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379,
119 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473,
120 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563,
121 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637,
122 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701,
123 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779,
124 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833,
125 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907,
126 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971,
127 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027,
128 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121,
129 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207,
130 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253,
131 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349,
132 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457,
133 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517,
134 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561,
135 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621,
136 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691,
137 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757,
138 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853,
139 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919,
140 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009,
141 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087,
142 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161,
143 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231,
144 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291,
145 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369,
146 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443,
147 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537,
148 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609,
149 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677,
150 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731,
151 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803,
152 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861,
153 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941,
154 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011,
155 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091,
156 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161,
157 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227,
158 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311,
159 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377,
160 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433,
161 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491,
162 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587,
163 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649,
164 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733,
165 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791,
166 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857,
167 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929,
168 9931, 9941, 9949, 9967, 9973, 10007, 10009, 10037,
169 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099,
170 10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163,
171 10169, 10177, 10181, 10193, 10211, 10223, 10243, 10247,
172 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303,
173 10313, 10321, 10331, 10333, 10337, 10343, 10357, 10369,
174 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459,
175 10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531,
176 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627,
177 10631, 10639, 10651, 10657, 10663, 10667, 10687, 10691,
178 10709, 10711, 10723, 10729, 10733, 10739, 10753, 10771,
179 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859,
180 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937,
181 10939, 10949, 10957, 10973, 10979, 10987, 10993, 11003,
182 11027, 11047, 11057, 11059, 11069, 11071, 11083, 11087,
183 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161,
184 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251,
185 11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317,
186 11321, 11329, 11351, 11353, 11369, 11383, 11393, 11399,
187 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483,
188 11489, 11491, 11497, 11503, 11519, 11527, 11549, 11551,
189 11579, 11587, 11593, 11597, 11617, 11621, 11633, 11657,
190 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731,
191 11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813,
192 11821, 11827, 11831, 11833, 11839, 11863, 11867, 11887,
193 11897, 11903, 11909, 11923, 11927, 11933, 11939, 11941,
194 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011,
195 12037, 12041, 12043, 12049, 12071, 12073, 12097, 12101,
196 12107, 12109, 12113, 12119, 12143, 12149, 12157, 12161,
197 12163, 12197, 12203, 12211, 12227, 12239, 12241, 12251,
198 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323,
199 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401,
200 12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473,
201 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527,
202 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589,
203 12601, 12611, 12613, 12619, 12637, 12641, 12647, 12653,
204 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739,
205 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821,
206 12823, 12829, 12841, 12853, 12889, 12893, 12899, 12907,
207 12911, 12917, 12919, 12923, 12941, 12953, 12959, 12967,
208 12973, 12979, 12983, 13001, 13003, 13007, 13009, 13033,
209 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109,
210 13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177,
211 13183, 13187, 13217, 13219, 13229, 13241, 13249, 13259,
212 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337,
213 13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421,
214 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499,
215 13513, 13523, 13537, 13553, 13567, 13577, 13591, 13597,
216 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681,
217 13687, 13691, 13693, 13697, 13709, 13711, 13721, 13723,
218 13729, 13751, 13757, 13759, 13763, 13781, 13789, 13799,
219 13807, 13829, 13831, 13841, 13859, 13873, 13877, 13879,
220 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933,
221 13963, 13967, 13997, 13999, 14009, 14011, 14029, 14033,
222 14051, 14057, 14071, 14081, 14083, 14087, 14107, 14143,
223 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221,
224 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323,
225 14327, 14341, 14347, 14369, 14387, 14389, 14401, 14407,
226 14411, 14419, 14423, 14431, 14437, 14447, 14449, 14461,
227 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549,
228 14551, 14557, 14561, 14563, 14591, 14593, 14621, 14627,
229 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699,
230 14713, 14717, 14723, 14731, 14737, 14741, 14747, 14753,
231 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821,
232 14827, 14831, 14843, 14851, 14867, 14869, 14879, 14887,
233 14891, 14897, 14923, 14929, 14939, 14947, 14951, 14957,
234 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073,
235 15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137,
236 15139, 15149, 15161, 15173, 15187, 15193, 15199, 15217,
237 15227, 15233, 15241, 15259, 15263, 15269, 15271, 15277,
238 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331,
239 15349, 15359, 15361, 15373, 15377, 15383, 15391, 15401,
240 15413, 15427, 15439, 15443, 15451, 15461, 15467, 15473,
241 15493, 15497, 15511, 15527, 15541, 15551, 15559, 15569,
242 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643,
243 15647, 15649, 15661, 15667, 15671, 15679, 15683, 15727,
244 15731, 15733, 15737, 15739, 15749, 15761, 15767, 15773,
245 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859,
246 15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919,
247 15923, 15937, 15959, 15971, 15973, 15991, 16001, 16007,
248 16033, 16057, 16061, 16063, 16067, 16069, 16073, 16087,
249 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183,
250 16187, 16189, 16193, 16217, 16223, 16229, 16231, 16249,
251 16253, 16267, 16273, 16301, 16319, 16333, 16339, 16349,
252 16361, 16363, 16369, 16381, 16411, 16417, 16421, 16427,
253 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493,
254 16519, 16529, 16547, 16553, 16561, 16567, 16573, 16603,
255 16607, 16619, 16631, 16633, 16649, 16651, 16657, 16661,
256 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747,
257 16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843,
258 16871, 16879, 16883, 16889, 16901, 16903, 16921, 16927,
259 16931, 16937, 16943, 16963, 16979, 16981, 16987, 16993,
260 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053,
261 17077, 17093, 17099, 17107, 17117, 17123, 17137, 17159,
262 17167, 17183, 17189, 17191, 17203, 17207, 17209, 17231,
263 17239, 17257, 17291, 17293, 17299, 17317, 17321, 17327,
264 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389,
265 17393, 17401, 17417, 17419, 17431, 17443, 17449, 17467,
266 17471, 17477, 17483, 17489, 17491, 17497, 17509, 17519,
267 17539, 17551, 17569, 17573, 17579, 17581, 17597, 17599,
268 17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683,
269 17707, 17713, 17729, 17737, 17747, 17749, 17761, 17783,
270 17789, 17791, 17807, 17827, 17837, 17839, 17851, 17863,