sshprime.c

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