putty/SSHPRIME.C

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