9 * This prime generation algorithm is pretty much cribbed from
10 * OpenSSL. The algorithm is:
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
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)
19 * - perform the Miller-Rabin primality test enough times to
20 * ensure the probability of it being composite is 2^-80 or
23 * - go back to square one if any M-R test fails.
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.
32 * Lemma: if a^2 == 1 (mod p), and p is prime, then either a == 1
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. []
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.
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
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)
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.)
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.
70 * So. 1729 - 1 equals 27 * 2^6. So we look at
72 * 2^27 mod 1729 == 645
73 * 2^108 mod 1729 == 1065
77 * 2^1728 mod 1729 == 1
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.
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.)
92 * Put simply, then, the Miller-Rabin test requires us to:
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
99 * 5. report failure otherwise.
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
110 * The first few odd primes.
116 * for i in range(n): z.append(1)
117 * for i in range(2,n):
120 * for j in range(i,n,i): z[j] = 0
122 * list = sieve(65535)
123 * for i in list[1:]: sys.stdout.write("%d," % i)
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,
828 #define NPRIMES (sizeof(primes) / sizeof(*primes))
831 * Generate a prime. We can deal with various extra properties of
834 * - to speed up use in RSA, we can arrange to select a prime with
835 * the property (prime % modulus) != residue.
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.
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
850 Bignum
primegen(int bits
, int modulus
, int residue
, Bignum factor
,
851 int phase
, progfn_t pfn
, void *pfnparam
, unsigned firstbits
)
853 int i
, k
, v
, byte
, bitsleft
, check
, checks
, fbsize
;
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
;
865 while (firstbits
>> fbsize
) /* work out how to align this */
870 pfn(pfnparam
, PROGFN_PROGRESS
, phase
, ++progress
);
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.
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;
886 bitsleft
= 8, byte
= random_byte();
891 bignum_set_bit(p
, i
, v
);
895 p
= bigmul(tmp
, factor
);
897 assert(bignum_bit(p
, 0) == 0);
898 bignum_set_bit(p
, 0, 1);
902 * Ensure this random number is coprime to the first few
903 * primes, by repeatedly adding either 2 or 2*factor to it
906 for (i
= 0; i
< NPRIMES
; i
++) {
907 moduli
[i
] = primes
[i
];
908 residues
[i
] = bignum_mod_short(p
, primes
[i
]);
910 multipliers
[i
] = bignum_mod_short(factor
, primes
[i
]);
914 moduli
[NPRIMES
] = modulus
;
915 residues
[NPRIMES
] = (bignum_mod_short(p
, (unsigned short) modulus
)
916 + modulus
- residue
);
918 multipliers
[NPRIMES
] = bignum_mod_short(factor
, modulus
);
920 multipliers
[NPRIMES
] = 1;
923 for (i
= 0; i
< (sizeof(moduli
) / sizeof(*moduli
)); i
++)
924 if (!((residues
[i
] + delta
* multipliers
[i
]) % moduli
[i
]))
926 if (i
< (sizeof(moduli
) / sizeof(*moduli
))) { /* we broke */
939 tmp
= bignum_from_long(delta
);
940 p
= bigmuladd(tmp
, factor
, q
);
943 p
= bignum_add_long(q
, delta
);
948 * Now apply the Miller-Rabin primality test a few times. First
949 * work out how many checks are needed.
976 * Next, write p-1 as q*2^k.
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. */
986 * Now, for each check ...
988 for (check
= 0; check
< checks
; check
++) {
992 * Invent a random number between 1 and p-1 inclusive.
995 w
= bn_power_2(bits
- 1);
996 for (i
= 0; i
< bits
; i
++) {
998 bitsleft
= 8, byte
= random_byte();
1002 bignum_set_bit(w
, i
, v
);
1004 bn_restore_invariant(w
);
1005 if (bignum_cmp(w
, p
) >= 0 || bignum_cmp(w
, Zero
) == 0) {
1012 pfn(pfnparam
, PROGFN_PROGRESS
, phase
, ++progress
);
1015 * Compute w^q mod p.
1017 wqp
= modpow(w
, q
, p
);
1021 * See if this is 1, or if it is -1, or if it becomes -1
1022 * when squared at most k-1 times.
1024 if (bignum_cmp(wqp
, One
) == 0 || bignum_cmp(wqp
, pm1
) == 0) {
1028 for (i
= 0; i
< k
- 1; i
++) {
1029 wqp2
= modmul(wqp
, wqp
, p
);
1032 if (bignum_cmp(wqp
, pm1
) == 0)
1041 * It didn't. Therefore, w is a witness for the
1042 * compositeness of p.
1060 * Invent a pair of values suitable for use as 'firstbits' in the
1061 * above function, such that their product is at least 2.
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!'
1073 void invent_firstbits(unsigned *one
, unsigned *two
)
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.
1083 *one
= 0x100 | random_byte();
1084 *two
= 0x100 | random_byte();
1085 } while (*one
* *two
< 0x20000);
