1/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2 * All rights reserved. 3 * 4 * This package is an SSL implementation written 5 * by Eric Young (eay@cryptsoft.com). 6 * The implementation was written so as to conform with Netscapes SSL. 7 * 8 * This library is free for commercial and non-commercial use as long as 9 * the following conditions are aheared to. The following conditions 10 * apply to all code found in this distribution, be it the RC4, RSA, 11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 12 * included with this distribution is covered by the same copyright terms 13 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 14 * 15 * Copyright remains Eric Young's, and as such any Copyright notices in 16 * the code are not to be removed. 17 * If this package is used in a product, Eric Young should be given attribution 18 * as the author of the parts of the library used. 19 * This can be in the form of a textual message at program startup or 20 * in documentation (online or textual) provided with the package. 21 * 22 * Redistribution and use in source and binary forms, with or without 23 * modification, are permitted provided that the following conditions 24 * are met: 25 * 1. Redistributions of source code must retain the copyright 26 * notice, this list of conditions and the following disclaimer. 27 * 2. Redistributions in binary form must reproduce the above copyright 28 * notice, this list of conditions and the following disclaimer in the 29 * documentation and/or other materials provided with the distribution. 30 * 3. All advertising materials mentioning features or use of this software 31 * must display the following acknowledgement: 32 * "This product includes cryptographic software written by 33 * Eric Young (eay@cryptsoft.com)" 34 * The word 'cryptographic' can be left out if the rouines from the library 35 * being used are not cryptographic related :-). 36 * 4. If you include any Windows specific code (or a derivative thereof) from 37 * the apps directory (application code) you must include an acknowledgement: 38 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 39 * 40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 50 * SUCH DAMAGE. 51 * 52 * The licence and distribution terms for any publically available version or 53 * derivative of this code cannot be changed. i.e. this code cannot simply be 54 * copied and put under another distribution licence 55 * [including the GNU Public Licence.] 56 */ 57/* ==================================================================== 58 * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved. 59 * 60 * Redistribution and use in source and binary forms, with or without 61 * modification, are permitted provided that the following conditions 62 * are met: 63 * 64 * 1. Redistributions of source code must retain the above copyright 65 * notice, this list of conditions and the following disclaimer. 66 * 67 * 2. Redistributions in binary form must reproduce the above copyright 68 * notice, this list of conditions and the following disclaimer in 69 * the documentation and/or other materials provided with the 70 * distribution. 71 * 72 * 3. All advertising materials mentioning features or use of this 73 * software must display the following acknowledgment: 74 * "This product includes software developed by the OpenSSL Project 75 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 76 * 77 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 78 * endorse or promote products derived from this software without 79 * prior written permission. For written permission, please contact 80 * openssl-core@openssl.org. 81 * 82 * 5. Products derived from this software may not be called "OpenSSL" 83 * nor may "OpenSSL" appear in their names without prior written 84 * permission of the OpenSSL Project. 85 * 86 * 6. Redistributions of any form whatsoever must retain the following 87 * acknowledgment: 88 * "This product includes software developed by the OpenSSL Project 89 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 90 * 91 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 92 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 93 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 94 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 95 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 96 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 97 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 98 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 99 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 100 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 101 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 102 * OF THE POSSIBILITY OF SUCH DAMAGE. 103 * ==================================================================== 104 * 105 * This product includes cryptographic software written by Eric Young 106 * (eay@cryptsoft.com). This product includes software written by Tim 107 * Hudson (tjh@cryptsoft.com). */ 108 109#include <openssl/bn.h> 110 111#include <openssl/err.h> 112#include <openssl/mem.h> 113 114#include "internal.h" 115 116/* number of Miller-Rabin iterations for an error rate of less than 2^-80 117 * for random 'b'-bit input, b >= 100 (taken from table 4.4 in the Handbook 118 * of Applied Cryptography [Menezes, van Oorschot, Vanstone; CRC Press 1996]; 119 * original paper: Damgaard, Landrock, Pomerance: Average case error estimates 120 * for the strong probable prime test. -- Math. Comp. 61 (1993) 177-194) */ 121#define BN_prime_checks_for_size(b) ((b) >= 1300 ? 2 : \ 122 (b) >= 850 ? 3 : \ 123 (b) >= 650 ? 4 : \ 124 (b) >= 550 ? 5 : \ 125 (b) >= 450 ? 6 : \ 126 (b) >= 400 ? 7 : \ 127 (b) >= 350 ? 8 : \ 128 (b) >= 300 ? 9 : \ 129 (b) >= 250 ? 12 : \ 130 (b) >= 200 ? 15 : \ 131 (b) >= 150 ? 18 : \ 132 /* b >= 100 */ 27) 133 134/* The quick sieve algorithm approach to weeding out primes is Philip 135 * Zimmermann's, as implemented in PGP. I have had a read of his comments and 136 * implemented my own version. */ 137 138/* NUMPRIMES is the number of primes that fit into a uint16_t. */ 139#define NUMPRIMES 2048 140 141/* primes is defined at the bottom of the file and contains all the primes that 142 * fit into a uint16_t. */ 143static const uint16_t primes[NUMPRIMES]; 144 145static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, 146 const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont); 147static int probable_prime(BIGNUM *rnd, int bits); 148static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, 149 const BIGNUM *rem, BN_CTX *ctx); 150static int probable_prime_dh_safe(BIGNUM *rnd, int bits, const BIGNUM *add, 151 const BIGNUM *rem, BN_CTX *ctx); 152 153void BN_GENCB_set(BN_GENCB *callback, 154 int (*f)(int event, int n, struct bn_gencb_st *), 155 void *arg) { 156 callback->callback = f; 157 callback->arg = arg; 158} 159 160int BN_GENCB_call(BN_GENCB *callback, int event, int n) { 161 if (!callback) { 162 return 1; 163 } 164 165 return callback->callback(event, n, callback); 166} 167 168int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add, 169 const BIGNUM *rem, BN_GENCB *cb) { 170 BIGNUM *t; 171 int found = 0; 172 int i, j, c1 = 0; 173 BN_CTX *ctx; 174 int checks = BN_prime_checks_for_size(bits); 175 176 if (bits < 2) { 177 /* There are no prime numbers this small. */ 178 OPENSSL_PUT_ERROR(BN, BN_generate_prime_ex, BN_R_BITS_TOO_SMALL); 179 return 0; 180 } else if (bits == 2 && safe) { 181 /* The smallest safe prime (7) is three bits. */ 182 OPENSSL_PUT_ERROR(BN, BN_generate_prime_ex, BN_R_BITS_TOO_SMALL); 183 return 0; 184 } 185 186 ctx = BN_CTX_new(); 187 if (ctx == NULL) { 188 goto err; 189 } 190 BN_CTX_start(ctx); 191 t = BN_CTX_get(ctx); 192 if (!t) { 193 goto err; 194 } 195 196loop: 197 /* make a random number and set the top and bottom bits */ 198 if (add == NULL) { 199 if (!probable_prime(ret, bits)) { 200 goto err; 201 } 202 } else { 203 if (safe) { 204 if (!probable_prime_dh_safe(ret, bits, add, rem, ctx)) { 205 goto err; 206 } 207 } else { 208 if (!probable_prime_dh(ret, bits, add, rem, ctx)) { 209 goto err; 210 } 211 } 212 } 213 214 if (!BN_GENCB_call(cb, BN_GENCB_GENERATED, c1++)) { 215 /* aborted */ 216 goto err; 217 } 218 219 if (!safe) { 220 i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb); 221 if (i == -1) { 222 goto err; 223 } else if (i == 0) { 224 goto loop; 225 } 226 } else { 227 /* for "safe prime" generation, check that (p-1)/2 is prime. Since a prime 228 * is odd, We just need to divide by 2 */ 229 if (!BN_rshift1(t, ret)) { 230 goto err; 231 } 232 233 for (i = 0; i < checks; i++) { 234 j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, NULL); 235 if (j == -1) { 236 goto err; 237 } else if (j == 0) { 238 goto loop; 239 } 240 241 j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, NULL); 242 if (j == -1) { 243 goto err; 244 } else if (j == 0) { 245 goto loop; 246 } 247 248 if (!BN_GENCB_call(cb, i, c1 - 1)) { 249 goto err; 250 } 251 /* We have a safe prime test pass */ 252 } 253 } 254 255 /* we have a prime :-) */ 256 found = 1; 257 258err: 259 if (ctx != NULL) { 260 BN_CTX_end(ctx); 261 BN_CTX_free(ctx); 262 } 263 264 return found; 265} 266 267int BN_primality_test(int *is_probably_prime, const BIGNUM *candidate, 268 int checks, BN_CTX *ctx, int do_trial_division, 269 BN_GENCB *cb) { 270 switch (BN_is_prime_fasttest_ex(candidate, checks, ctx, do_trial_division, cb)) { 271 case 1: 272 *is_probably_prime = 1; 273 return 1; 274 case 0: 275 *is_probably_prime = 0; 276 return 1; 277 default: 278 *is_probably_prime = 0; 279 return 0; 280 } 281} 282 283int BN_is_prime_ex(const BIGNUM *candidate, int checks, BN_CTX *ctx, BN_GENCB *cb) { 284 return BN_is_prime_fasttest_ex(candidate, checks, ctx, 0, cb); 285} 286 287int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, 288 int do_trial_division, BN_GENCB *cb) { 289 int i, j, ret = -1; 290 int k; 291 BN_CTX *ctx = NULL; 292 BIGNUM *A1, *A1_odd, *check; /* taken from ctx */ 293 BN_MONT_CTX *mont = NULL; 294 const BIGNUM *A = NULL; 295 296 if (BN_cmp(a, BN_value_one()) <= 0) { 297 return 0; 298 } 299 300 if (checks == BN_prime_checks) { 301 checks = BN_prime_checks_for_size(BN_num_bits(a)); 302 } 303 304 /* first look for small factors */ 305 if (!BN_is_odd(a)) { 306 /* a is even => a is prime if and only if a == 2 */ 307 return BN_is_word(a, 2); 308 } 309 310 if (do_trial_division) { 311 for (i = 1; i < NUMPRIMES; i++) { 312 if (BN_mod_word(a, primes[i]) == 0) { 313 return 0; 314 } 315 } 316 317 if (!BN_GENCB_call(cb, 1, -1)) { 318 goto err; 319 } 320 } 321 322 if (ctx_passed != NULL) { 323 ctx = ctx_passed; 324 } else if ((ctx = BN_CTX_new()) == NULL) { 325 goto err; 326 } 327 BN_CTX_start(ctx); 328 329 /* A := abs(a) */ 330 if (a->neg) { 331 BIGNUM *t; 332 if ((t = BN_CTX_get(ctx)) == NULL) { 333 goto err; 334 } 335 BN_copy(t, a); 336 t->neg = 0; 337 A = t; 338 } else { 339 A = a; 340 } 341 342 A1 = BN_CTX_get(ctx); 343 A1_odd = BN_CTX_get(ctx); 344 check = BN_CTX_get(ctx); 345 if (check == NULL) { 346 goto err; 347 } 348 349 /* compute A1 := A - 1 */ 350 if (!BN_copy(A1, A)) { 351 goto err; 352 } 353 if (!BN_sub_word(A1, 1)) { 354 goto err; 355 } 356 if (BN_is_zero(A1)) { 357 ret = 0; 358 goto err; 359 } 360 361 /* write A1 as A1_odd * 2^k */ 362 k = 1; 363 while (!BN_is_bit_set(A1, k)) { 364 k++; 365 } 366 if (!BN_rshift(A1_odd, A1, k)) { 367 goto err; 368 } 369 370 /* Montgomery setup for computations mod A */ 371 mont = BN_MONT_CTX_new(); 372 if (mont == NULL) { 373 goto err; 374 } 375 if (!BN_MONT_CTX_set(mont, A, ctx)) { 376 goto err; 377 } 378 379 for (i = 0; i < checks; i++) { 380 if (!BN_pseudo_rand_range(check, A1)) { 381 goto err; 382 } 383 if (!BN_add_word(check, 1)) { 384 goto err; 385 } 386 /* now 1 <= check < A */ 387 388 j = witness(check, A, A1, A1_odd, k, ctx, mont); 389 if (j == -1) { 390 goto err; 391 } 392 if (j) { 393 ret = 0; 394 goto err; 395 } 396 if (!BN_GENCB_call(cb, 1, i)) { 397 goto err; 398 } 399 } 400 ret = 1; 401 402err: 403 if (ctx != NULL) { 404 BN_CTX_end(ctx); 405 if (ctx_passed == NULL) { 406 BN_CTX_free(ctx); 407 } 408 } 409 if (mont != NULL) { 410 BN_MONT_CTX_free(mont); 411 } 412 413 return ret; 414} 415 416static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, 417 const BIGNUM *a1_odd, int k, BN_CTX *ctx, 418 BN_MONT_CTX *mont) { 419 if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) { /* w := w^a1_odd mod a */ 420 return -1; 421 } 422 if (BN_is_one(w)) { 423 return 0; /* probably prime */ 424 } 425 if (BN_cmp(w, a1) == 0) { 426 return 0; /* w == -1 (mod a), 'a' is probably prime */ 427 } 428 429 while (--k) { 430 if (!BN_mod_mul(w, w, w, a, ctx)) { /* w := w^2 mod a */ 431 return -1; 432 } 433 434 if (BN_is_one(w)) { 435 return 1; /* 'a' is composite, otherwise a previous 'w' would 436 * have been == -1 (mod 'a') */ 437 } 438 439 if (BN_cmp(w, a1) == 0) { 440 return 0; /* w == -1 (mod a), 'a' is probably prime */ 441 } 442 } 443 444 /* If we get here, 'w' is the (a-1)/2-th power of the original 'w', 445 * and it is neither -1 nor +1 -- so 'a' cannot be prime */ 446 return 1; 447} 448 449static BN_ULONG get_word(const BIGNUM *bn) { 450 if (bn->top == 1) { 451 return bn->d[0]; 452 } 453 return 0; 454} 455 456static int probable_prime(BIGNUM *rnd, int bits) { 457 int i; 458 uint16_t mods[NUMPRIMES]; 459 BN_ULONG delta; 460 BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1]; 461 char is_single_word = bits <= BN_BITS2; 462 463again: 464 if (!BN_rand(rnd, bits, 1, 1)) { 465 return 0; 466 } 467 468 /* we now have a random number 'rnd' to test. */ 469 for (i = 1; i < NUMPRIMES; i++) { 470 mods[i] = (uint16_t)BN_mod_word(rnd, (BN_ULONG)primes[i]); 471 } 472 /* If bits is so small that it fits into a single word then we 473 * additionally don't want to exceed that many bits. */ 474 if (is_single_word) { 475 BN_ULONG size_limit = (((BN_ULONG)1) << bits) - get_word(rnd) - 1; 476 if (size_limit < maxdelta) { 477 maxdelta = size_limit; 478 } 479 } 480 delta = 0; 481 482loop: 483 if (is_single_word) { 484 BN_ULONG rnd_word = get_word(rnd); 485 486 /* In the case that the candidate prime is a single word then 487 * we check that: 488 * 1) It's greater than primes[i] because we shouldn't reject 489 * 3 as being a prime number because it's a multiple of 490 * three. 491 * 2) That it's not a multiple of a known prime. We don't 492 * check that rnd-1 is also coprime to all the known 493 * primes because there aren't many small primes where 494 * that's true. */ 495 for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) { 496 if ((mods[i] + delta) % primes[i] == 0) { 497 delta += 2; 498 if (delta > maxdelta) 499 goto again; 500 goto loop; 501 } 502 } 503 } else { 504 for (i = 1; i < NUMPRIMES; i++) { 505 /* check that rnd is not a prime and also 506 * that gcd(rnd-1,primes) == 1 (except for 2) */ 507 if (((mods[i] + delta) % primes[i]) <= 1) { 508 delta += 2; 509 if (delta > maxdelta) 510 goto again; 511 goto loop; 512 } 513 } 514 } 515 516 if (!BN_add_word(rnd, delta)) { 517 return 0; 518 } 519 if (BN_num_bits(rnd) != bits) { 520 goto again; 521 } 522 523 return 1; 524} 525 526static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, 527 const BIGNUM *rem, BN_CTX *ctx) { 528 int i, ret = 0; 529 BIGNUM *t1; 530 531 BN_CTX_start(ctx); 532 if ((t1 = BN_CTX_get(ctx)) == NULL) { 533 goto err; 534 } 535 536 if (!BN_rand(rnd, bits, 0, 1)) { 537 goto err; 538 } 539 540 /* we need ((rnd-rem) % add) == 0 */ 541 542 if (!BN_mod(t1, rnd, add, ctx)) { 543 goto err; 544 } 545 if (!BN_sub(rnd, rnd, t1)) { 546 goto err; 547 } 548 if (rem == NULL) { 549 if (!BN_add_word(rnd, 1)) { 550 goto err; 551 } 552 } else { 553 if (!BN_add(rnd, rnd, rem)) { 554 goto err; 555 } 556 } 557 /* we now have a random number 'rand' to test. */ 558 559loop: 560 for (i = 1; i < NUMPRIMES; i++) { 561 /* check that rnd is a prime */ 562 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) { 563 if (!BN_add(rnd, rnd, add)) { 564 goto err; 565 } 566 goto loop; 567 } 568 } 569 570 ret = 1; 571 572err: 573 BN_CTX_end(ctx); 574 return ret; 575} 576 577static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, 578 const BIGNUM *rem, BN_CTX *ctx) { 579 int i, ret = 0; 580 BIGNUM *t1, *qadd, *q; 581 582 bits--; 583 BN_CTX_start(ctx); 584 t1 = BN_CTX_get(ctx); 585 q = BN_CTX_get(ctx); 586 qadd = BN_CTX_get(ctx); 587 if (qadd == NULL) { 588 goto err; 589 } 590 591 if (!BN_rshift1(qadd, padd)) { 592 goto err; 593 } 594 595 if (!BN_rand(q, bits, 0, 1)) { 596 goto err; 597 } 598 599 /* we need ((rnd-rem) % add) == 0 */ 600 if (!BN_mod(t1, q, qadd, ctx)) { 601 goto err; 602 } 603 604 if (!BN_sub(q, q, t1)) { 605 goto err; 606 } 607 608 if (rem == NULL) { 609 if (!BN_add_word(q, 1)) { 610 goto err; 611 } 612 } else { 613 if (!BN_rshift1(t1, rem)) { 614 goto err; 615 } 616 if (!BN_add(q, q, t1)) { 617 goto err; 618 } 619 } 620 621 /* we now have a random number 'rand' to test. */ 622 if (!BN_lshift1(p, q)) { 623 goto err; 624 } 625 if (!BN_add_word(p, 1)) { 626 goto err; 627 } 628 629loop: 630 for (i = 1; i < NUMPRIMES; i++) { 631 /* check that p and q are prime */ 632 /* check that for p and q 633 * gcd(p-1,primes) == 1 (except for 2) */ 634 if ((BN_mod_word(p, (BN_ULONG)primes[i]) == 0) || 635 (BN_mod_word(q, (BN_ULONG)primes[i]) == 0)) { 636 if (!BN_add(p, p, padd)) { 637 goto err; 638 } 639 if (!BN_add(q, q, qadd)) { 640 goto err; 641 } 642 goto loop; 643 } 644 } 645 646 ret = 1; 647 648err: 649 BN_CTX_end(ctx); 650 return ret; 651} 652 653static const uint16_t primes[NUMPRIMES] = { 654 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 655 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 656 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 657 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 658 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 659 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 660 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 661 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 662 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 663 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 664 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 665 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 666 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 667 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 668 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 669 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 670 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 671 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 672 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 673 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 674 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 675 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 676 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 677 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 678 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 679 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 680 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 681 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 682 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 683 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 684 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 685 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 686 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 687 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 688 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 689 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 690 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 691 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 692 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 693 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 694 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 695 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 696 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 697 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 698 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 699 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 700 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 701 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 702 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 703 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 704 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 705 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 706 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 707 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 708 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 709 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 710 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 711 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 712 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 713 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 714 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 715 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 716 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 717 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 718 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 719 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 720 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 721 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 722 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 723 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 724 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 725 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 726 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 727 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 728 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 729 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 730 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 731 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 732 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 733 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 734 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 735 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 736 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 737 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 738 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 739 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 740 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 741 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 742 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 743 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 744 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 745 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 746 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 747 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 748 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 749 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 750 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 751 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 752 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 753 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 754 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 755 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 756 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 757 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 758 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 759 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 760 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 761 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 762 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 763 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 764 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 765 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007, 10009, 10037, 766 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111, 10133, 767 10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223, 768 10243, 10247, 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313, 769 10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429, 770 10433, 10453, 10457, 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529, 771 10531, 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639, 772 10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733, 773 10739, 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859, 774 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949, 10957, 775 10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059, 11069, 11071, 776 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161, 11171, 777 11173, 11177, 11197, 11213, 11239, 11243, 11251, 11257, 11261, 11273, 11279, 778 11287, 11299, 11311, 11317, 11321, 11329, 11351, 11353, 11369, 11383, 11393, 779 11399, 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483, 11489, 11491, 780 11497, 11503, 11519, 11527, 11549, 11551, 11579, 11587, 11593, 11597, 11617, 781 11621, 11633, 11657, 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731, 782 11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831, 783 11833, 11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933, 784 11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037, 785 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109, 12113, 12119, 786 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211, 12227, 12239, 12241, 787 12251, 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323, 12329, 12343, 788 12347, 12373, 12377, 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437, 789 12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527, 790 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611, 12613, 791 12619, 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713, 792 12721, 12739, 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 793 12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923, 794 12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 13009, 795 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121, 13127, 796 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187, 13217, 13219, 13229, 797 13241, 13249, 13259, 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337, 798 13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441, 13451, 13457, 799 13463, 13469, 13477, 13487, 13499, 13513, 13523, 13537, 13553, 13567, 13577, 800 13591, 13597, 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681, 13687, 801 13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759, 802 13763, 13781, 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877, 803 13879, 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967, 804 13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081, 14083, 805 14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221, 806 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323, 14327, 14341, 14347, 807 14369, 14387, 14389, 14401, 14407, 14411, 14419, 14423, 14431, 14437, 14447, 808 14449, 14461, 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549, 14551, 809 14557, 14561, 14563, 14591, 14593, 14621, 14627, 14629, 14633, 14639, 14653, 810 14657, 14669, 14683, 14699, 14713, 14717, 14723, 14731, 14737, 14741, 14747, 811 14753, 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831, 812 14843, 14851, 14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939, 813 14947, 14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073, 814 15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149, 15161, 815 15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259, 15263, 15269, 816 15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331, 15349, 817 15359, 15361, 15373, 15377, 15383, 15391, 15401, 15413, 15427, 15439, 15443, 818 15451, 15461, 15467, 15473, 15493, 15497, 15511, 15527, 15541, 15551, 15559, 819 15569, 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643, 15647, 15649, 820 15661, 15667, 15671, 15679, 15683, 15727, 15731, 15733, 15737, 15739, 15749, 821 15761, 15767, 15773, 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859, 822 15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959, 823 15971, 15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069, 824 16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183, 16187, 825 16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267, 16273, 16301, 826 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381, 16411, 16417, 16421, 827 16427, 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493, 16519, 16529, 828 16547, 16553, 16561, 16567, 16573, 16603, 16607, 16619, 16631, 16633, 16649, 829 16651, 16657, 16661, 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747, 830 16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843, 16871, 16879, 16883, 831 16889, 16901, 16903, 16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981, 832 16987, 16993, 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077, 833 17093, 17099, 17107, 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191, 834 17203, 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317, 17321, 835 17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389, 17393, 17401, 836 17417, 17419, 17431, 17443, 17449, 17467, 17471, 17477, 17483, 17489, 17491, 837 17497, 17509, 17519, 17539, 17551, 17569, 17573, 17579, 17581, 17597, 17599, 838 17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683, 17707, 17713, 17729, 839 17737, 17747, 17749, 17761, 17783, 17789, 17791, 17807, 17827, 17837, 17839, 840 17851, 17863, }; 841