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