sshprime.c

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