8 * This prime generation algorithm is pretty much cribbed from
9 * OpenSSL. The algorithm is:
11 * - invent a B-bit random number and ensure the top and bottom
12 * bits are set (so it's definitely B-bit, and it's definitely
15 * - see if it's coprime to all primes below 2^16; increment it by
16 * two until it is (this shouldn't take long in general)
18 * - perform the Miller-Rabin primality test enough times to
19 * ensure the probability of it being composite is 2^-80 or
22 * - go back to square one if any M-R test fails.
26 * The Miller-Rabin primality test is an extension to the Fermat
27 * test. The Fermat test just checks that a^(p-1) == 1 mod p; this
28 * is vulnerable to Carmichael numbers. Miller-Rabin considers how
29 * that 1 is derived as well.
31 * Lemma: if a^2 == 1 (mod p), and p is prime, then either a == 1
34 * Proof: p divides a^2-1, i.e. p divides (a+1)(a-1). Hence,
35 * since p is prime, either p divides (a+1) or p divides (a-1).
36 * But this is the same as saying that either a is congruent to
37 * -1 mod p or a is congruent to +1 mod p. []
39 * Comment: This fails when p is not prime. Consider p=mn, so
40 * that mn divides (a+1)(a-1). Now we could have m dividing (a+1)
41 * and n dividing (a-1), without the whole of mn dividing either.
42 * For example, consider a=10 and p=99. 99 = 9 * 11; 9 divides
43 * 10-1 and 11 divides 10+1, so a^2 is congruent to 1 mod p
44 * without a having to be congruent to either 1 or -1.
46 * So the Miller-Rabin test, as well as considering a^(p-1),
47 * considers a^((p-1)/2), a^((p-1)/4), and so on as far as it can
48 * go. In other words. we write p-1 as q * 2^k, with k as large as
49 * possible (i.e. q must be odd), and we consider the powers
51 * a^(q*2^0) a^(q*2^1) ... a^(q*2^(k-1)) a^(q*2^k)
52 * i.e. a^((n-1)/2^k) a^((n-1)/2^(k-1)) ... a^((n-1)/2) a^(n-1)
54 * If p is to be prime, the last of these must be 1. Therefore, by
55 * the above lemma, the one before it must be either 1 or -1. And
56 * _if_ it's 1, then the one before that must be either 1 or -1,
57 * and so on ... In other words, we expect to see a trailing chain
58 * of 1s preceded by a -1. (If we're unlucky, our trailing chain of
59 * 1s will be as long as the list so we'll never get to see what
60 * lies before it. This doesn't count as a test failure because it
61 * hasn't _proved_ that p is not prime.)
63 * For example, consider a=2 and p=1729. 1729 is a Carmichael
64 * number: although it's not prime, it satisfies a^(p-1) == 1 mod p
65 * for any a coprime to it. So the Fermat test wouldn't have a
66 * problem with it at all, unless we happened to stumble on an a
67 * which had a common factor.
69 * So. 1729 - 1 equals 27 * 2^6. So we look at
71 * 2^27 mod 1729 == 645
72 * 2^108 mod 1729 == 1065
76 * 2^1728 mod 1729 == 1
78 * We do have a trailing string of 1s, so the Fermat test would
79 * have been happy. But this trailing string of 1s is preceded by
80 * 1065; whereas if 1729 were prime, we'd expect to see it preceded
81 * by -1 (i.e. 1728.). Guards! Seize this impostor.
83 * (If we were unlucky, we might have tried a=16 instead of a=2;
84 * now 16^27 mod 1729 == 1, so we would have seen a long string of
85 * 1s and wouldn't have seen the thing _before_ the 1s. So, just
86 * like the Fermat test, for a given p there may well exist values
87 * of a which fail to show up its compositeness. So we try several,
88 * just like the Fermat test. The difference is that Miller-Rabin
89 * is not _in general_ fooled by Carmichael numbers.)
91 * Put simply, then, the Miller-Rabin test requires us to:
93 * 1. write p-1 as q * 2^k, with q odd
94 * 2. compute z = (a^q) mod p.
95 * 3. report success if z == 1 or z == -1.
96 * 4. square z at most k-1 times, and report success if it becomes
98 * 5. report failure otherwise.
100 * (We expect z to become -1 after at most k-1 squarings, because
101 * if it became -1 after k squarings then a^(p-1) would fail to be
102 * 1. And we don't need to investigate what happens after we see a
103 * -1, because we _know_ that -1 squared is 1 modulo anything at
104 * all, so after we've seen a -1 we can be sure of seeing nothing
109 * The first few odd primes.
115 * for i in range(n): z.append(1)
116 * for i in range(2,n):
119 * for j in range(i,n,i): z[j] = 0
121 * list = sieve(65535)
122 * for i in list[1:]: sys.stdout.write("%d," % i)
124 static const unsigned short primes[] = {
125 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
126 71, 73, 79, 83, 89, 97, 101,
127 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
129 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271,
131 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
133 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491,
135 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613,
137 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
139 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857,
141 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
143 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087,
145 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187,
147 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289,
149 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409,
151 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489,
153 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597,
155 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697,
157 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801,
159 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913,
161 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027,
163 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131,
165 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251,
167 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351,
169 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447,
171 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591,
173 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689,
175 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789,
177 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897,
179 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019,
181 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163,
183 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259,
185 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371,
187 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499,
189 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593,
191 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701,
193 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823,
195 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929,
197 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051,
199 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159,
201 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273,
203 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421,
205 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523,
207 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651,
209 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787,
211 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919,
213 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009,
215 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119,
217 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273,
219 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407,
221 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503,
223 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641,
225 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741,
227 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851,
229 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987,
231 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113,
233 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229,
235 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337,
237 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469,
239 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599,
241 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719,
243 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841,
245 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967,
247 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079,
249 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219,
251 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351,
253 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507,
255 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591,
257 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717,
259 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867,
261 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993,
263 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117,
265 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243,
267 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377,
269 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527,
271 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647,
273 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747,
275 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863,
277 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007,
279 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137,
281 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257,
283 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391,
285 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479,
287 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629,
289 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749,
291 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859,
293 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007,
295 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111,
297 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223,
299 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313, 10321,
301 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429, 10433, 10453,
303 10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531, 10559, 10567,
305 10601, 10607, 10613, 10627, 10631, 10639, 10651, 10657, 10663, 10667,
307 10709, 10711, 10723, 10729, 10733, 10739, 10753, 10771, 10781, 10789,
309 10837, 10847, 10853, 10859, 10861, 10867, 10883, 10889, 10891, 10903,
311 10939, 10949, 10957, 10973, 10979, 10987, 10993, 11003, 11027, 11047,
313 11069, 11071, 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149,
315 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251, 11257, 11261,
317 11287, 11299, 11311, 11317, 11321, 11329, 11351, 11353, 11369, 11383,
319 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483, 11489, 11491,
321 11519, 11527, 11549, 11551, 11579, 11587, 11593, 11597, 11617, 11621,
323 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731, 11743, 11777,
325 11789, 11801, 11807, 11813, 11821, 11827, 11831, 11833, 11839, 11863,
327 11897, 11903, 11909, 11923, 11927, 11933, 11939, 11941, 11953, 11959,
329 11981, 11987, 12007, 12011, 12037, 12041, 12043, 12049, 12071, 12073,
331 12107, 12109, 12113, 12119, 12143, 12149, 12157, 12161, 12163, 12197,
333 12227, 12239, 12241, 12251, 12253, 12263, 12269, 12277, 12281, 12289,
335 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401, 12409, 12413,
337 12437, 12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511,
339 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611,
341 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713,
343 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 12829,
345 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923, 12941, 12953,
347 12973, 12979, 12983, 13001, 13003, 13007, 13009, 13033, 13037, 13043,
349 13093, 13099, 13103, 13109, 13121, 13127, 13147, 13151, 13159, 13163,
351 13183, 13187, 13217, 13219, 13229, 13241, 13249, 13259, 13267, 13291,
353 13313, 13327, 13331, 13337, 13339, 13367, 13381, 13397, 13399, 13411,
355 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499, 13513, 13523,
357 13567, 13577, 13591, 13597, 13613, 13619, 13627, 13633, 13649, 13669,
359 13687, 13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729, 13751,
361 13763, 13781, 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873,
363 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967,
365 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081, 14083, 14087,
367 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221, 14243, 14249,
369 14293, 14303, 14321, 14323, 14327, 14341, 14347, 14369, 14387, 14389,
371 14411, 14419, 14423, 14431, 14437, 14447, 14449, 14461, 14479, 14489,
373 14533, 14537, 14543, 14549, 14551, 14557, 14561, 14563, 14591, 14593,
375 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699, 14713, 14717,
377 14737, 14741, 14747, 14753, 14759, 14767, 14771, 14779, 14783, 14797,
379 14827, 14831, 14843, 14851, 14867, 14869, 14879, 14887, 14891, 14897,
381 14939, 14947, 14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053,
383 15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149,
385 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259, 15263, 15269,
387 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331, 15349, 15359,
389 15377, 15383, 15391, 15401, 15413, 15427, 15439, 15443, 15451, 15461,
391 15493, 15497, 15511, 15527, 15541, 15551, 15559, 15569, 15581, 15583,
393 15619, 15629, 15641, 15643, 15647, 15649, 15661, 15667, 15671, 15679,
395 15731, 15733, 15737, 15739, 15749, 15761, 15767, 15773, 15787, 15791,
397 15809, 15817, 15823, 15859, 15877, 15881, 15887, 15889, 15901, 15907,
399 15923, 15937, 15959, 15971, 15973, 15991, 16001, 16007, 16033, 16057,
401 16067, 16069, 16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139,
403 16187, 16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267,
405 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381, 16411, 16417,
407 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493, 16519, 16529,
409 16561, 16567, 16573, 16603, 16607, 16619, 16631, 16633, 16649, 16651,
411 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747, 16759, 16763,
413 16823, 16829, 16831, 16843, 16871, 16879, 16883, 16889, 16901, 16903,
415 16931, 16937, 16943, 16963, 16979, 16981, 16987, 16993, 17011, 17021,
417 17033, 17041, 17047, 17053, 17077, 17093, 17099, 17107, 17117, 17123,
419 17167, 17183, 17189, 17191, 17203, 17207, 17209, 17231, 17239, 17257,
421 17299, 17317, 17321, 17327, 17333, 17341, 17351, 17359, 17377, 17383,
423 17393, 17401, 17417, 17419, 17431, 17443, 17449, 17467, 17471, 17477,
425 17491, 17497, 17509, 17519, 17539, 17551, 17569, 17573, 17579, 17581,
427 17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683, 17707, 17713,
429 17747, 17749, 17761, 17783, 17789, 17791, 17807, 17827, 17837, 17839,
431 17881, 17891, 17903, 17909, 17911, 17921, 17923, 17929, 17939, 17957,
433 17977, 17981, 17987, 17989, 18013, 18041, 18043, 18047, 18049, 18059,
435 18089, 18097, 18119, 18121, 18127, 18131, 18133, 18143, 18149, 18169,
437 18199, 18211, 18217, 18223, 18229, 18233, 18251, 18253, 18257, 18269,
439 18301, 18307, 18311, 18313, 18329, 18341, 18353, 18367, 18371, 18379,
441 18413, 18427, 18433, 18439, 18443, 18451, 18457, 18461, 18481, 18493,
443 18521, 18523, 18539, 18541, 18553, 18583, 18587, 18593, 18617, 18637,
445 18679, 18691, 18701, 18713, 18719, 18731, 18743, 18749, 18757, 18773,
447 18797, 18803, 18839, 18859, 18869, 18899, 18911, 18913, 18917, 18919,
449 18973, 18979, 19001, 19009, 19013, 19031, 19037, 19051, 19069, 19073,
451 19087, 19121, 19139, 19141, 19157, 19163, 19181, 19183, 19207, 19211,
453 19231, 19237, 19249, 19259, 19267, 19273, 19289, 19301, 19309, 19319,
455 19379, 19381, 19387, 19391, 19403, 19417, 19421, 19423, 19427, 19429,
457 19447, 19457, 19463, 19469, 19471, 19477, 19483, 19489, 19501, 19507,
459 19543, 19553, 19559, 19571, 19577, 19583, 19597, 19603, 19609, 19661,
461 19697, 19699, 19709, 19717, 19727, 19739, 19751, 19753, 19759, 19763,
463 19801, 19813, 19819, 19841, 19843, 19853, 19861, 19867, 19889, 19891,
465 19927, 19937, 19949, 19961, 19963, 19973, 19979, 19991, 19993, 19997,
467 20023, 20029, 20047, 20051, 20063, 20071, 20089, 20101, 20107, 20113,
469 20129, 20143, 20147, 20149, 20161, 20173, 20177, 20183, 20201, 20219,
471 20249, 20261, 20269, 20287, 20297, 20323, 20327, 20333, 20341, 20347,
473 20359, 20369, 20389, 20393, 20399, 20407, 20411, 20431, 20441, 20443,
475 20483, 20507, 20509, 20521, 20533, 20543, 20549, 20551, 20563, 20593,
477 20627, 20639, 20641, 20663, 20681, 20693, 20707, 20717, 20719, 20731,
479 20749, 20753, 20759, 20771, 20773, 20789, 20807, 20809, 20849, 20857,
481 20887, 20897, 20899, 20903, 20921, 20929, 20939, 20947, 20959, 20963,
483 21001, 21011, 21013, 21017, 21019, 21023, 21031, 21059, 21061, 21067,
485 21107, 21121, 21139, 21143, 21149, 21157, 21163, 21169, 21179, 21187,
487 21211, 21221, 21227, 21247, 21269, 21277, 21283, 21313, 21317, 21319,
489 21347, 21377, 21379, 21383, 21391, 21397, 21401, 21407, 21419, 21433,
491 21487, 21491, 21493, 21499, 21503, 21517, 21521, 21523, 21529, 21557,
493 21569, 21577, 21587, 21589, 21599, 21601, 21611, 21613, 21617, 21647,
495 21673, 21683, 21701, 21713, 21727, 21737, 21739, 21751, 21757, 21767,
497 21799, 21803, 21817, 21821, 21839, 21841, 21851, 21859, 21863, 21871,
499 21911, 21929, 21937, 21943, 21961, 21977, 21991, 21997, 22003, 22013,
501 22037, 22039, 22051, 22063, 22067, 22073, 22079, 22091, 22093, 22109,
503 22129, 22133, 22147, 22153, 22157, 22159, 22171, 22189, 22193, 22229,
505 22271, 22273, 22277, 22279, 22283, 22291, 22303, 22307, 22343, 22349,
507 22381, 22391, 22397, 22409, 22433, 22441, 22447, 22453, 22469, 22481,
509 22511, 22531, 22541, 22543, 22549, 22567, 22571, 22573, 22613, 22619,
511 22639, 22643, 22651, 22669, 22679, 22691, 22697, 22699, 22709, 22717,
513 22739, 22741, 22751, 22769, 22777, 22783, 22787, 22807, 22811, 22817,
515 22861, 22871, 22877, 22901, 22907, 22921, 22937, 22943, 22961, 22963,
517 23003, 23011, 23017, 23021, 23027, 23029, 23039, 23041, 23053, 23057,
519 23071, 23081, 23087, 23099, 23117, 23131, 23143, 23159, 23167, 23173,
521 23201, 23203, 23209, 23227, 23251, 23269, 23279, 23291, 23293, 23297,
523 23327, 23333, 23339, 23357, 23369, 23371, 23399, 23417, 23431, 23447,
525 23497, 23509, 23531, 23537, 23539, 23549, 23557, 23561, 23563, 23567,
527 23599, 23603, 23609, 23623, 23627, 23629, 23633, 23663, 23669, 23671,
529 23689, 23719, 23741, 23743, 23747, 23753, 23761, 23767, 23773, 23789,
531 23819, 23827, 23831, 23833, 23857, 23869, 23873, 23879, 23887, 23893,
533 23911, 23917, 23929, 23957, 23971, 23977, 23981, 23993, 24001, 24007,
535 24029, 24043, 24049, 24061, 24071, 24077, 24083, 24091, 24097, 24103,
537 24113, 24121, 24133, 24137, 24151, 24169, 24179, 24181, 24197, 24203,
539 24239, 24247, 24251, 24281, 24317, 24329, 24337, 24359, 24371, 24373,
541 24407, 24413, 24419, 24421, 24439, 24443, 24469, 24473, 24481, 24499,
543 24527, 24533, 24547, 24551, 24571, 24593, 24611, 24623, 24631, 24659,
545 24683, 24691, 24697, 24709, 24733, 24749, 24763, 24767, 24781, 24793,
547 24821, 24841, 24847, 24851, 24859, 24877, 24889, 24907, 24917, 24919,
549 24953, 24967, 24971, 24977, 24979, 24989, 25013, 25031, 25033, 25037,
551 25087, 25097, 25111, 25117, 25121, 25127, 25147, 25153, 25163, 25169,
553 25189, 25219, 25229, 25237, 25243, 25247, 25253, 25261, 25301, 25303,
555 25321, 25339, 25343, 25349, 25357, 25367, 25373, 25391, 25409, 25411,
557 25447, 25453, 25457, 25463, 25469, 25471, 25523, 25537, 25541, 25561,
559 25583, 25589, 25601, 25603, 25609, 25621, 25633, 25639, 25643, 25657,
561 25679, 25693, 25703, 25717, 25733, 25741, 25747, 25759, 25763, 25771,
563 25801, 25819, 25841, 25847, 25849, 25867, 25873, 25889, 25903, 25913,
565 25933, 25939, 25943, 25951, 25969, 25981, 25997, 25999, 26003, 26017,
567 26041, 26053, 26083, 26099, 26107, 26111, 26113, 26119, 26141, 26153,
569 26177, 26183, 26189, 26203, 26209, 26227, 26237, 26249, 26251, 26261,
571 26293, 26297, 26309, 26317, 26321, 26339, 26347, 26357, 26371, 26387,
573 26407, 26417, 26423, 26431, 26437, 26449, 26459, 26479, 26489, 26497,
575 26539, 26557, 26561, 26573, 26591, 26597, 26627, 26633, 26641, 26647,
577 26683, 26687, 26693, 26699, 26701, 26711, 26713, 26717, 26723, 26729,
579 26759, 26777, 26783, 26801, 26813, 26821, 26833, 26839, 26849, 26861,
581 26881, 26891, 26893, 26903, 26921, 26927, 26947, 26951, 26953, 26959,
583 26993, 27011, 27017, 27031, 27043, 27059, 27061, 27067, 27073, 27077,
585 27107, 27109, 27127, 27143, 27179, 27191, 27197, 27211, 27239, 27241,
587 27271, 27277, 27281, 27283, 27299, 27329, 27337, 27361, 27367, 27397,
589 27427, 27431, 27437, 27449, 27457, 27479, 27481, 27487, 27509, 27527,
591 27541, 27551, 27581, 27583, 27611, 27617, 27631, 27647, 27653, 27673,
593 27697, 27701, 27733, 27737, 27739, 27743, 27749, 27751, 27763, 27767,
595 27791, 27793, 27799, 27803, 27809, 27817, 27823, 27827, 27847, 27851,
597 27901, 27917, 27919, 27941, 27943, 27947, 27953, 27961, 27967, 27983,
599 28019, 28027, 28031, 28051, 28057, 28069, 28081, 28087, 28097, 28099,
601 28123, 28151, 28163, 28181, 28183, 28201, 28211, 28219, 28229, 28277,
603 28289, 28297, 28307, 28309, 28319, 28349, 28351, 28387, 28393, 28403,
605 28429, 28433, 28439, 28447, 28463, 28477, 28493, 28499, 28513, 28517,
607 28547, 28549, 28559, 28571, 28573, 28579, 28591, 28597, 28603, 28607,
609 28627, 28631, 28643, 28649, 28657, 28661, 28663, 28669, 28687, 28697,
611 28723, 28729, 28751, 28753, 28759, 28771, 28789, 28793, 28807, 28813,
613 28843, 28859, 28867, 28871, 28879, 28901, 28909, 28921, 28927, 28933,
615 28979, 29009, 29017, 29021, 29023, 29027, 29033, 29059, 29063, 29077,
617 29129, 29131, 29137, 29147, 29153, 29167, 29173, 29179, 29191, 29201,
619 29221, 29231, 29243, 29251, 29269, 29287, 29297, 29303, 29311, 29327,
621 29347, 29363, 29383, 29387, 29389, 29399, 29401, 29411, 29423, 29429,
623 29453, 29473, 29483, 29501, 29527, 29531, 29537, 29567, 29569, 29573,
625 29599, 29611, 29629, 29633, 29641, 29663, 29669, 29671, 29683, 29717,
627 29753, 29759, 29761, 29789, 29803, 29819, 29833, 29837, 29851, 29863,
629 29879, 29881, 29917, 29921, 29927, 29947, 29959, 29983, 29989, 30011,
631 30047, 30059, 30071, 30089, 30091, 30097, 30103, 30109, 30113, 30119,
633 30139, 30161, 30169, 30181, 30187, 30197, 30203, 30211, 30223, 30241,
635 30269, 30271, 30293, 30307, 30313, 30319, 30323, 30341, 30347, 30367,
637 30403, 30427, 30431, 30449, 30467, 30469, 30491, 30493, 30497, 30509,
639 30539, 30553, 30557, 30559, 30577, 30593, 30631, 30637, 30643, 30649,
641 30677, 30689, 30697, 30703, 30707, 30713, 30727, 30757, 30763, 30773,
643 30809, 30817, 30829, 30839, 30841, 30851, 30853, 30859, 30869, 30871,
645 30911, 30931, 30937, 30941, 30949, 30971, 30977, 30983, 31013, 31019,
647 31051, 31063, 31069, 31079, 31081, 31091, 31121, 31123, 31139, 31147,
649 31159, 31177, 31181, 31183, 31189, 31193, 31219, 31223, 31231, 31237,
651 31253, 31259, 31267, 31271, 31277, 31307, 31319, 31321, 31327, 31333,
653 31379, 31387, 31391, 31393, 31397, 31469, 31477, 31481, 31489, 31511,
655 31531, 31541, 31543, 31547, 31567, 31573, 31583, 31601, 31607, 31627,
657 31657, 31663, 31667, 31687, 31699, 31721, 31723, 31727, 31729, 31741,
659 31771, 31793, 31799, 31817, 31847, 31849, 31859, 31873, 31883, 31891,
661 31963, 31973, 31981, 31991, 32003, 32009, 32027, 32029, 32051, 32057,
663 32069, 32077, 32083, 32089, 32099, 32117, 32119, 32141, 32143, 32159,
665 32189, 32191, 32203, 32213, 32233, 32237, 32251, 32257, 32261, 32297,
667 32309, 32321, 32323, 32327, 32341, 32353, 32359, 32363, 32369, 32371,
669 32401, 32411, 32413, 32423, 32429, 32441, 32443, 32467, 32479, 32491,
671 32507, 32531, 32533, 32537, 32561, 32563, 32569, 32573, 32579, 32587,
673 32611, 32621, 32633, 32647, 32653, 32687, 32693, 32707, 32713, 32717,
675 32771, 32779, 32783, 32789, 32797, 32801, 32803, 32831, 32833, 32839,
677 32887, 32909, 32911, 32917, 32933, 32939, 32941, 32957, 32969, 32971,
679 32993, 32999, 33013, 33023, 33029, 33037, 33049, 33053, 33071, 33073,
681 33107, 33113, 33119, 33149, 33151, 33161, 33179, 33181, 33191, 33199,
683 33223, 33247, 33287, 33289, 33301, 33311, 33317, 33329, 33331, 33343,
685 33353, 33359, 33377, 33391, 33403, 33409, 33413, 33427, 33457, 33461,
687 33487, 33493, 33503, 33521, 33529, 33533, 33547, 33563, 33569, 33577,
689 33589, 33599, 33601, 33613, 33617, 33619, 33623, 33629, 33637, 33641,
691 33703, 33713, 33721, 33739, 33749, 33751, 33757, 33767, 33769, 33773,
693 33809, 33811, 33827, 33829, 33851, 33857, 33863, 33871, 33889, 33893,
695 33931, 33937, 33941, 33961, 33967, 33997, 34019, 34031, 34033, 34039,
697 34123, 34127, 34129, 34141, 34147, 34157, 34159, 34171, 34183, 34211,
699 34231, 34253, 34259, 34261, 34267, 34273, 34283, 34297, 34301, 34303,
701 34327, 34337, 34351, 34361, 34367, 34369, 34381, 34403, 34421, 34429,
703 34469, 34471, 34483, 34487, 34499, 34501, 34511, 34513, 34519, 34537,
705 34583, 34589, 34591, 34603, 34607, 34613, 34631, 34649, 34651, 34667,
707 34687, 34693, 34703, 34721, 34729, 34739, 34747, 34757, 34759, 34763,
709 34819, 34841, 34843, 34847, 34849, 34871, 34877, 34883, 34897, 34913,
711 34949, 34961, 34963, 34981, 35023, 35027, 35051, 35053, 35059, 35069,
713 35089, 35099, 35107, 35111, 35117, 35129, 35141, 35149, 35153, 35159,
715 35221, 35227, 35251, 35257, 35267, 35279, 35281, 35291, 35311, 35317,
717 35339, 35353, 35363, 35381, 35393, 35401, 35407, 35419, 35423, 35437,
719 35461, 35491, 35507, 35509, 35521, 35527, 35531, 35533, 35537, 35543,
721 35591, 35593, 35597, 35603, 35617, 35671, 35677, 35729, 35731, 35747,
723 35771, 35797, 35801, 35803, 35809, 35831, 35837, 35839, 35851, 35863,
725 35897, 35899, 35911, 35923, 35933, 35951, 35963, 35969, 35977, 35983,
727 36007, 36011, 36013, 36017, 36037, 36061, 36067, 36073, 36083, 36097,
729 36131, 36137, 36151, 36161, 36187, 36191, 36209, 36217, 36229, 36241,
731 36269, 36277, 36293, 36299, 36307, 36313, 36319, 36341, 36343, 36353,
733 36389, 36433, 36451, 36457, 36467, 36469, 36473, 36479, 36493, 36497,
735 36529, 36541, 36551, 36559, 36563, 36571, 36583, 36587, 36599, 36607,
737 36643, 36653, 36671, 36677, 36683, 36691, 36697, 36709, 36713, 36721,
739 36761, 36767, 36779, 36781, 36787, 36791, 36793, 36809, 36821, 36833,
741 36871, 36877, 36887, 36899, 36901, 36913, 36919, 36923, 36929, 36931,
743 36973, 36979, 36997, 37003, 37013, 37019, 37021, 37039, 37049, 37057,
745 37097, 37117, 37123, 37139, 37159, 37171, 37181, 37189, 37199, 37201,
747 37243, 37253, 37273, 37277, 37307, 37309, 37313, 37321, 37337, 37339,
749 37363, 37369, 37379, 37397, 37409, 37423, 37441, 37447, 37463, 37483,
751 37501, 37507, 37511, 37517, 37529, 37537, 37547, 37549, 37561, 37567,
753 37579, 37589, 37591, 37607, 37619, 37633, 37643, 37649, 37657, 37663,
755 37699, 37717, 37747, 37781, 37783, 37799, 37811, 37813, 37831, 37847,
757 37871, 37879, 37889, 37897, 37907, 37951, 37957, 37963, 37967, 37987,
759 37997, 38011, 38039, 38047, 38053, 38069, 38083, 38113, 38119, 38149,
761 38177, 38183, 38189, 38197, 38201, 38219, 38231, 38237, 38239, 38261,
763 38287, 38299, 38303, 38317, 38321, 38327, 38329, 38333, 38351, 38371,
765 38431, 38447, 38449, 38453, 38459, 38461, 38501, 38543, 38557, 38561,
767 38593, 38603, 38609, 38611, 38629, 38639, 38651, 38653, 38669, 38671,
769 38699, 38707, 38711, 38713, 38723, 38729, 38737, 38747, 38749, 38767,
771 38803, 38821, 38833, 38839, 38851, 38861, 38867, 38873, 38891, 38903,
773 38923, 38933, 38953, 38959, 38971, 38977, 38993, 39019, 39023, 39041,
775 39079, 39089, 39097, 39103, 39107, 39113, 39119, 39133, 39139, 39157,
777 39181, 39191, 39199, 39209, 39217, 39227, 39229, 39233, 39239, 39241,
779 39301, 39313, 39317, 39323, 39341, 39343, 39359, 39367, 39371, 39373,
781 39409, 39419, 39439, 39443, 39451, 39461, 39499, 39503, 39509, 39511,
783 39551, 39563, 39569, 39581, 39607, 39619, 39623, 39631, 39659, 39667,
785 39703, 39709, 39719, 39727, 39733, 39749, 39761, 39769, 39779, 39791,
787 39827, 39829, 39839, 39841, 39847, 39857, 39863, 39869, 39877, 39883,
789 39929, 39937, 39953, 39971, 39979, 39983, 39989, 40009, 40013, 40031,
791 40063, 40087, 40093, 40099, 40111, 40123, 40127, 40129, 40151, 40153,
793 40177, 40189, 40193, 40213, 40231, 40237, 40241, 40253, 40277, 40283,
795 40351, 40357, 40361, 40387, 40423, 40427, 40429, 40433, 40459, 40471,
797 40493, 40499, 40507, 40519, 40529, 40531, 40543, 40559, 40577, 40583,
799 40609, 40627, 40637, 40639, 40693, 40697, 40699, 40709, 40739, 40751,
801 40771, 40787, 40801, 40813, 40819, 40823, 40829, 40841, 40847, 40849,
803 40879, 40883, 40897, 40903, 40927, 40933, 40939, 40949, 40961, 40973,
805 41017, 41023, 41039, 41047, 41051, 41057, 41077, 41081, 41113, 41117,
807 41143, 41149, 41161, 41177, 41179, 41183, 41189, 41201, 41203, 41213,
809 41231, 41233, 41243, 41257, 41263, 41269, 41281, 41299, 41333, 41341,
811 41381, 41387, 41389, 41399, 41411, 41413, 41443, 41453, 41467, 41479,
813 41513, 41519, 41521, 41539, 41543, 41549, 41579, 41593, 41597, 41603,
815 41617, 41621, 41627, 41641, 41647, 41651, 41659, 41669, 41681, 41687,
817 41737, 41759, 41761, 41771, 41777, 41801, 41809, 41813, 41843, 41849,
819 41879, 41887, 41893, 41897, 41903, 41911, 41927, 41941, 41947, 41953,
821 41969, 41981, 41983, 41999, 42013, 42017, 42019, 42023, 42043, 42061,
823 42083, 42089, 42101, 42131, 42139, 42157, 42169, 42179, 42181, 42187,
825 42209, 42221, 42223, 42227, 42239, 42257, 42281, 42283, 42293, 42299,
827 42331, 42337, 42349, 42359, 42373, 42379, 42391, 42397, 42403, 42407,
829 42437, 42443, 42451, 42457, 42461, 42463, 42467, 42473, 42487, 42491,
831 42533, 42557, 42569, 42571, 42577, 42589, 42611, 42641, 42643, 42649,
833 42683, 42689, 42697, 42701, 42703, 42709, 42719, 42727, 42737, 42743,
835 42773, 42787, 42793, 42797, 42821, 42829, 42839, 42841, 42853, 42859,
837 42901, 42923, 42929, 42937, 42943, 42953, 42961, 42967, 42979, 42989,
839 43019, 43037, 43049, 43051, 43063, 43067, 43093, 43103, 43117, 43133,
841 43177, 43189, 43201, 43207, 43223, 43237, 43261, 43271, 43283, 43291,
843 43321, 43331, 43391, 43397, 43399, 43403, 43411, 43427, 43441, 43451,
845 43487, 43499, 43517, 43541, 43543, 43573, 43577, 43579, 43591, 43597,
847 43613, 43627, 43633, 43649, 43651, 43661, 43669, 43691, 43711, 43717,
849 43759, 43777, 43781, 43783, 43787, 43789, 43793, 43801, 43853, 43867,
851 43913, 43933, 43943, 43951, 43961, 43963, 43969, 43973, 43987, 43991,
853 44021, 44027, 44029, 44041, 44053, 44059, 44071, 44087, 44089, 44101,
855 44123, 44129, 44131, 44159, 44171, 44179, 44189, 44201, 44203, 44207,
857 44257, 44263, 44267, 44269, 44273, 44279, 44281, 44293, 44351, 44357,
859 44383, 44389, 44417, 44449, 44453, 44483, 44491, 44497, 44501, 44507,
861 44533, 44537, 44543, 44549, 44563, 44579, 44587, 44617, 44621, 44623,
863 44647, 44651, 44657, 44683, 44687, 44699, 44701, 44711, 44729, 44741,
865 44773, 44777, 44789, 44797, 44809, 44819, 44839, 44843, 44851, 44867,
867 44893, 44909, 44917, 44927, 44939, 44953, 44959, 44963, 44971, 44983,
869 45013, 45053, 45061, 45077, 45083, 45119, 45121, 45127, 45131, 45137,
871 45179, 45181, 45191, 45197, 45233, 45247, 45259, 45263, 45281, 45289,
873 45317, 45319, 45329, 45337, 45341, 45343, 45361, 45377, 45389, 45403,
875 45433, 45439, 45481, 45491, 45497, 45503, 45523, 45533, 45541, 45553,
877 45587, 45589, 45599, 45613, 45631, 45641, 45659, 45667, 45673, 45677,
879 45707, 45737, 45751, 45757, 45763, 45767, 45779, 45817, 45821, 45823,
881 45841, 45853, 45863, 45869, 45887, 45893, 45943, 45949, 45953, 45959,
883 45989, 46021, 46027, 46049, 46051, 46061, 46073, 46091, 46093, 46099,
885 46141, 46147, 46153, 46171, 46181, 46183, 46187, 46199, 46219, 46229,
887 46271, 46273, 46279, 46301, 46307, 46309, 46327, 46337, 46349, 46351,
889 46411, 46439, 46441, 46447, 46451, 46457, 46471, 46477, 46489, 46499,
891 46523, 46549, 46559, 46567, 46573, 46589, 46591, 46601, 46619, 46633,
893 46649, 46663, 46679, 46681, 46687, 46691, 46703, 46723, 46727, 46747,
895 46769, 46771, 46807, 46811, 46817, 46819, 46829, 46831, 46853, 46861,
897 46889, 46901, 46919, 46933, 46957, 46993, 46997, 47017, 47041, 47051,
899 47087, 47093, 47111, 47119, 47123, 47129, 47137, 47143, 47147, 47149,
901 47207, 47221, 47237, 47251, 47269, 47279, 47287, 47293, 47297, 47303,
903 47339, 47351, 47353, 47363, 47381, 47387, 47389, 47407, 47417, 47419,
905 47459, 47491, 47497, 47501, 47507, 47513, 47521, 47527, 47533, 47543,
907 47581, 47591, 47599, 47609, 47623, 47629, 47639, 47653, 47657, 47659,
909 47701, 47711, 47713, 47717, 47737, 47741, 47743, 47777, 47779, 47791,
911 47809, 47819, 47837, 47843, 47857, 47869, 47881, 47903, 47911, 47917,
913 47947, 47951, 47963, 47969, 47977, 47981, 48017, 48023, 48029, 48049,
915 48091, 48109, 48119, 48121, 48131, 48157, 48163, 48179, 48187, 48193,
917 48239, 48247, 48259, 48271, 48281, 48299, 48311, 48313, 48337, 48341,
919 48383, 48397, 48407, 48409, 48413, 48437, 48449, 48463, 48473, 48479,
921 48491, 48497, 48523, 48527, 48533, 48539, 48541, 48563, 48571, 48589,
923 48619, 48623, 48647, 48649, 48661, 48673, 48677, 48679, 48731, 48733,
925 48761, 48767, 48779, 48781, 48787, 48799, 48809, 48817, 48821, 48823,
927 48859, 48869, 48871, 48883, 48889, 48907, 48947, 48953, 48973, 48989,
929 49009, 49019, 49031, 49033, 49037, 49043, 49057, 49069, 49081, 49103,
931 49121, 49123, 49139, 49157, 49169, 49171, 49177, 49193, 49199, 49201,
933 49223, 49253, 49261, 49277, 49279, 49297, 49307, 49331, 49333, 49339,
935 49369, 49391, 49393, 49409, 49411, 49417, 49429, 49433, 49451, 49459,
937 49481, 49499, 49523, 49529, 49531, 49537, 49547, 49549, 49559, 49597,
939 49627, 49633, 49639, 49663, 49667, 49669, 49681, 49697, 49711, 49727,
941 49747, 49757, 49783, 49787, 49789, 49801, 49807, 49811, 49823, 49831,
943 49871, 49877, 49891, 49919, 49921, 49927, 49937, 49939, 49943, 49957,
945 49999, 50021, 50023, 50033, 50047, 50051, 50053, 50069, 50077, 50087,
947 50111, 50119, 50123, 50129, 50131, 50147, 50153, 50159, 50177, 50207,
949 50231, 50261, 50263, 50273, 50287, 50291, 50311, 50321, 50329, 50333,
951 50363, 50377, 50383, 50387, 50411, 50417, 50423, 50441, 50459, 50461,
953 50513, 50527, 50539, 50543, 50549, 50551, 50581, 50587, 50591, 50593,
955 50647, 50651, 50671, 50683, 50707, 50723, 50741, 50753, 50767, 50773,
957 50821, 50833, 50839, 50849, 50857, 50867, 50873, 50891, 50893, 50909,
959 50951, 50957, 50969, 50971, 50989, 50993, 51001, 51031, 51043, 51047,
961 51071, 51109, 51131, 51133, 51137, 51151, 51157, 51169, 51193, 51197,
963 51217, 51229, 51239, 51241, 51257, 51263, 51283, 51287, 51307, 51329,
965 51347, 51349, 51361, 51383, 51407, 51413, 51419, 51421, 51427, 51431,
967 51449, 51461, 51473, 51479, 51481, 51487, 51503, 51511, 51517, 51521,
969 51563, 51577, 51581, 51593, 51599, 51607, 51613, 51631, 51637, 51647,
971 51679, 51683, 51691, 51713, 51719, 51721, 51749, 51767, 51769, 51787,
973 51817, 51827, 51829, 51839, 51853, 51859, 51869, 51871, 51893, 51899,
975 51929, 51941, 51949, 51971, 51973, 51977, 51991, 52009, 52021, 52027,
977 52067, 52069, 52081, 52103, 52121, 52127, 52147, 52153, 52163, 52177,
979 52189, 52201, 52223, 52237, 52249, 52253, 52259, 52267, 52289, 52291,
981 52321, 52361, 52363, 52369, 52379, 52387, 52391, 52433, 52453, 52457,
983 52511, 52517, 52529, 52541, 52543, 52553, 52561, 52567, 52571, 52579,
985 52627, 52631, 52639, 52667, 52673, 52691, 52697, 52709, 52711, 52721,
987 52747, 52757, 52769, 52783, 52807, 52813, 52817, 52837, 52859, 52861,
989 52889, 52901, 52903, 52919, 52937, 52951, 52957, 52963, 52967, 52973,
991 53003, 53017, 53047, 53051, 53069, 53077, 53087, 53089, 53093, 53101,
993 53129, 53147, 53149, 53161, 53171, 53173, 53189, 53197, 53201, 53231,
995 53267, 53269, 53279, 53281, 53299, 53309, 53323, 53327, 53353, 53359,
997 53401, 53407, 53411, 53419, 53437, 53441, 53453, 53479, 53503, 53507,
999 53551, 53569, 53591, 53593, 53597, 53609, 53611, 53617, 53623, 53629,
1001 53653, 53657, 53681, 53693, 53699, 53717, 53719, 53731, 53759, 53773,
1003 53791, 53813, 53819, 53831, 53849, 53857, 53861, 53881, 53887, 53891,
1005 53917, 53923, 53927, 53939, 53951, 53959, 53987, 53993, 54001, 54011,
1007 54049, 54059, 54083, 54091, 54101, 54121, 54133, 54139, 54151, 54163,
1009 54193, 54217, 54251, 54269, 54277, 54287, 54293, 54311, 54319, 54323,
1011 54361, 54367, 54371, 54377, 54401, 54403, 54409, 54413, 54419, 54421,
1013 54449, 54469, 54493, 54497, 54499, 54503, 54517, 54521, 54539, 54541,
1015 54563, 54577, 54581, 54583, 54601, 54617, 54623, 54629, 54631, 54647,
1017 54679, 54709, 54713, 54721, 54727, 54751, 54767, 54773, 54779, 54787,
1019 54833, 54851, 54869, 54877, 54881, 54907, 54917, 54919, 54941, 54949,
1021 54979, 54983, 55001, 55009, 55021, 55049, 55051, 55057, 55061, 55073,
1023 55109, 55117, 55127, 55147, 55163, 55171, 55201, 55207, 55213, 55217,
1025 55243, 55249, 55259, 55291, 55313, 55331, 55333, 55337, 55339, 55343,
1027 55381, 55399, 55411, 55439, 55441, 55457, 55469, 55487, 55501, 55511,
1029 55547, 55579, 55589, 55603, 55609, 55619, 55621, 55631, 55633, 55639,
1031 55667, 55673, 55681, 55691, 55697, 55711, 55717, 55721, 55733, 55763,
1033 55799, 55807, 55813, 55817, 55819, 55823, 55829, 55837, 55843, 55849,
1035 55897, 55901, 55903, 55921, 55927, 55931, 55933, 55949, 55967, 55987,
1037 56009, 56039, 56041, 56053, 56081, 56087, 56093, 56099, 56101, 56113,
1039 56149, 56167, 56171, 56179, 56197, 56207, 56209, 56237, 56239, 56249,
1041 56269, 56299, 56311, 56333, 56359, 56369, 56377, 56383, 56393, 56401,
1043 56437, 56443, 56453, 56467, 56473, 56477, 56479, 56489, 56501, 56503,
1045 56527, 56531, 56533, 56543, 56569, 56591, 56597, 56599, 56611, 56629,
1047 56663, 56671, 56681, 56687, 56701, 56711, 56713, 56731, 56737, 56747,
1049 56779, 56783, 56807, 56809, 56813, 56821, 56827, 56843, 56857, 56873,
1051 56897, 56909, 56911, 56921, 56923, 56929, 56941, 56951, 56957, 56963,
1053 56993, 56999, 57037, 57041, 57047, 57059, 57073, 57077, 57089, 57097,
1055 57131, 57139, 57143, 57149, 57163, 57173, 57179, 57191, 57193, 57203,
1057 57241, 57251, 57259, 57269, 57271, 57283, 57287, 57301, 57329, 57331,
1059 57367, 57373, 57383, 57389, 57397, 57413, 57427, 57457, 57467, 57487,
1061 57527, 57529, 57557, 57559, 57571, 57587, 57593, 57601, 57637, 57641,
1063 57667, 57679, 57689, 57697, 57709, 57713, 57719, 57727, 57731, 57737,
1065 57781, 57787, 57791, 57793, 57803, 57809, 57829, 57839, 57847, 57853,
1067 57899, 57901, 57917, 57923, 57943, 57947, 57973, 57977, 57991, 58013,
1069 58043, 58049, 58057, 58061, 58067, 58073, 58099, 58109, 58111, 58129,
1071 58153, 58169, 58171, 58189, 58193, 58199, 58207, 58211, 58217, 58229,
1073 58243, 58271, 58309, 58313, 58321, 58337, 58363, 58367, 58369, 58379,
1075 58403, 58411, 58417, 58427, 58439, 58441, 58451, 58453, 58477, 58481,
1077 58543, 58549, 58567, 58573, 58579, 58601, 58603, 58613, 58631, 58657,
1079 58687, 58693, 58699, 58711, 58727, 58733, 58741, 58757, 58763, 58771,
1081 58831, 58889, 58897, 58901, 58907, 58909, 58913, 58921, 58937, 58943,
1083 58979, 58991, 58997, 59009, 59011, 59021, 59023, 59029, 59051, 59053,
1085 59077, 59083, 59093, 59107, 59113, 59119, 59123, 59141, 59149, 59159,
1087 59197, 59207, 59209, 59219, 59221, 59233, 59239, 59243, 59263, 59273,
1089 59341, 59351, 59357, 59359, 59369, 59377, 59387, 59393, 59399, 59407,
1091 59441, 59443, 59447, 59453, 59467, 59471, 59473, 59497, 59509, 59513,
1093 59561, 59567, 59581, 59611, 59617, 59621, 59627, 59629, 59651, 59659,
1095 59671, 59693, 59699, 59707, 59723, 59729, 59743, 59747, 59753, 59771,
1097 59797, 59809, 59833, 59863, 59879, 59887, 59921, 59929, 59951, 59957,
1099 59999, 60013, 60017, 60029, 60037, 60041, 60077, 60083, 60089, 60091,
1101 60107, 60127, 60133, 60139, 60149, 60161, 60167, 60169, 60209, 60217,
1103 60257, 60259, 60271, 60289, 60293, 60317, 60331, 60337, 60343, 60353,
1105 60397, 60413, 60427, 60443, 60449, 60457, 60493, 60497, 60509, 60521,
1107 60589, 60601, 60607, 60611, 60617, 60623, 60631, 60637, 60647, 60649,
1109 60679, 60689, 60703, 60719, 60727, 60733, 60737, 60757, 60761, 60763,
1111 60793, 60811, 60821, 60859, 60869, 60887, 60889, 60899, 60901, 60913,
1113 60923, 60937, 60943, 60953, 60961, 61001, 61007, 61027, 61031, 61043,
1115 61091, 61099, 61121, 61129, 61141, 61151, 61153, 61169, 61211, 61223,
1117 61261, 61283, 61291, 61297, 61331, 61333, 61339, 61343, 61357, 61363,
1119 61403, 61409, 61417, 61441, 61463, 61469, 61471, 61483, 61487, 61493,
1121 61519, 61543, 61547, 61553, 61559, 61561, 61583, 61603, 61609, 61613,
1123 61637, 61643, 61651, 61657, 61667, 61673, 61681, 61687, 61703, 61717,
1125 61751, 61757, 61781, 61813, 61819, 61837, 61843, 61861, 61871, 61879,
1127 61933, 61949, 61961, 61967, 61979, 61981, 61987, 61991, 62003, 62011,
1129 62047, 62053, 62057, 62071, 62081, 62099, 62119, 62129, 62131, 62137,
1131 62171, 62189, 62191, 62201, 62207, 62213, 62219, 62233, 62273, 62297,
1133 62311, 62323, 62327, 62347, 62351, 62383, 62401, 62417, 62423, 62459,
1135 62477, 62483, 62497, 62501, 62507, 62533, 62539, 62549, 62563, 62581,
1137 62603, 62617, 62627, 62633, 62639, 62653, 62659, 62683, 62687, 62701,
1139 62743, 62753, 62761, 62773, 62791, 62801, 62819, 62827, 62851, 62861,
1141 62897, 62903, 62921, 62927, 62929, 62939, 62969, 62971, 62981, 62983,
1143 63029, 63031, 63059, 63067, 63073, 63079, 63097, 63103, 63113, 63127,
1145 63179, 63197, 63199, 63211, 63241, 63247, 63277, 63281, 63299, 63311,
1147 63331, 63337, 63347, 63353, 63361, 63367, 63377, 63389, 63391, 63397,
1149 63421, 63439, 63443, 63463, 63467, 63473, 63487, 63493, 63499, 63521,
1151 63541, 63559, 63577, 63587, 63589, 63599, 63601, 63607, 63611, 63617,
1153 63649, 63659, 63667, 63671, 63689, 63691, 63697, 63703, 63709, 63719,
1155 63743, 63761, 63773, 63781, 63793, 63799, 63803, 63809, 63823, 63839,
1157 63857, 63863, 63901, 63907, 63913, 63929, 63949, 63977, 63997, 64007,
1159 64033, 64037, 64063, 64067, 64081, 64091, 64109, 64123, 64151, 64153,
1161 64187, 64189, 64217, 64223, 64231, 64237, 64271, 64279, 64283, 64301,
1163 64327, 64333, 64373, 64381, 64399, 64403, 64433, 64439, 64451, 64453,
1165 64499, 64513, 64553, 64567, 64577, 64579, 64591, 64601, 64609, 64613,
1167 64633, 64661, 64663, 64667, 64679, 64693, 64709, 64717, 64747, 64763,
1169 64793, 64811, 64817, 64849, 64853, 64871, 64877, 64879, 64891, 64901,
1171 64927, 64937, 64951, 64969, 64997, 65003, 65011, 65027, 65029, 65033,
1173 65071, 65089, 65099, 65101, 65111, 65119, 65123, 65129, 65141, 65147,
1175 65173, 65179, 65183, 65203, 65213, 65239, 65257, 65267, 65269, 65287,
1177 65323, 65327, 65353, 65357, 65371, 65381, 65393, 65407, 65413, 65419,
1179 65447, 65449, 65479, 65497, 65519, 65521,
1182 #define NPRIMES (sizeof(primes) / sizeof(*primes))
1185 * Generate a prime. We arrange to select a prime with the property
1186 * (prime % modulus) != residue (to speed up use in RSA).
1188 Bignum primegen(int bits, int modulus, int residue,
1189 int phase, progfn_t pfn, void *pfnparam)
1191 int i, k, v, byte, bitsleft, check, checks;
1192 unsigned long delta, moduli[NPRIMES + 1], residues[NPRIMES + 1];
1193 Bignum p, pm1, q, wqp, wqp2;
1201 pfn(pfnparam, phase, ++progress);
1204 * Generate a k-bit random number with top and bottom bits set.
1206 p = bn_power_2(bits - 1);
1207 for (i = 0; i < bits; i++) {
1208 if (i == 0 || i == bits - 1)
1212 bitsleft = 8, byte = random_byte();
1217 bignum_set_bit(p, i, v);
1221 * Ensure this random number is coprime to the first few
1222 * primes, by repeatedly adding 2 to it until it is.
1224 for (i = 0; i < NPRIMES; i++) {
1225 moduli[i] = primes[i];
1226 residues[i] = bignum_mod_short(p, primes[i]);
1228 moduli[NPRIMES] = modulus;
1229 residues[NPRIMES] = (bignum_mod_short(p, (unsigned short) modulus)
1230 + modulus - residue);
1233 for (i = 0; i < (sizeof(moduli) / sizeof(*moduli)); i++)
1234 if (!((residues[i] + delta) % moduli[i]))
1236 if (i < (sizeof(moduli) / sizeof(*moduli))) { /* we broke */
1247 p = bignum_add_long(q, delta);
1251 * Now apply the Miller-Rabin primality test a few times. First
1252 * work out how many checks are needed.
1279 * Next, write p-1 as q*2^k.
1281 for (k = 0; bignum_bit(p, k) == !k; k++); /* find first 1 bit in p-1 */
1282 q = bignum_rshift(p, k);
1283 /* And store p-1 itself, which we'll need. */
1288 * Now, for each check ...
1290 for (check = 0; check < checks; check++) {
1294 * Invent a random number between 1 and p-1 inclusive.
1297 w = bn_power_2(bits - 1);
1298 for (i = 0; i < bits; i++) {
1300 bitsleft = 8, byte = random_byte();
1304 bignum_set_bit(w, i, v);
1306 bn_restore_invariant(w);
1307 if (bignum_cmp(w, p) >= 0 || bignum_cmp(w, Zero) == 0) {
1314 pfn(pfnparam, phase, ++progress);
1317 * Compute w^q mod p.
1319 wqp = modpow(w, q, p);
1323 * See if this is 1, or if it is -1, or if it becomes -1
1324 * when squared at most k-1 times.
1326 if (bignum_cmp(wqp, One) == 0 || bignum_cmp(wqp, pm1) == 0) {
1330 for (i = 0; i < k - 1; i++) {
1331 wqp2 = modmul(wqp, wqp, p);
1334 if (bignum_cmp(wqp, pm1) == 0)
1343 * It didn't. Therefore, w is a witness for the
1344 * compositeness of p.