Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/Crypto/Util/number.py: 84%

1# 

2# number.py : Number-theoretic functions 

3# 

4# Part of the Python Cryptography Toolkit 

5# 

6# Written by Andrew M. Kuchling, Barry A. Warsaw, and others 

7# 

8# =================================================================== 

9# The contents of this file are dedicated to the public domain. To 

10# the extent that dedication to the public domain is not available, 

11# everyone is granted a worldwide, perpetual, royalty-free, 

12# non-exclusive license to exercise all rights associated with the 

13# contents of this file for any purpose whatsoever. 

14# No rights are reserved. 

15# 

16# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 

17# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 

18# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 

19# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 

20# BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 

21# ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 

22# CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 

23# SOFTWARE. 

24# =================================================================== 

25# 

26 

27__revision__ = "$Id$" 

28 

29from Crypto.pct_warnings import GetRandomNumber_DeprecationWarning, PowmInsecureWarning 

30from warnings import warn as _warn 

31import math 

32import sys 

33from Crypto.Util.py3compat import * 

34 

35bignum = int 

36try: 

37 from Crypto.PublicKey import _fastmath 

38except ImportError: 

39 # For production, we are going to let import issues due to gmp/mpir shared 

40 # libraries not loading slide silently and use slowmath. If you'd rather 

41 # see an exception raised if _fastmath exists but cannot be imported, 

42 # uncomment the below 

43 # 

44 # from distutils.sysconfig import get_config_var 

45 # import inspect, os 

46 # _fm_path = os.path.normpath(os.path.dirname(os.path.abspath( 

47 # inspect.getfile(inspect.currentframe()))) 

48 # +"/../../PublicKey/_fastmath"+get_config_var("SO")) 

49 # if os.path.exists(_fm_path): 

50 # raise ImportError("While the _fastmath module exists, importing "+ 

51 # "it failed. This may point to the gmp or mpir shared library "+ 

52 # "not being in the path. _fastmath was found at "+_fm_path) 

53 _fastmath = None 

54 

55# You need libgmp v5 or later to get mpz_powm_sec. Warn if it's not available. 

56if _fastmath is not None and not _fastmath.HAVE_DECL_MPZ_POWM_SEC: 

57 _warn("Not using mpz_powm_sec. You should rebuild using libgmp >= 5 to avoid timing attack vulnerability.", PowmInsecureWarning) 

58 

59# New functions 

60from ._number_new import * 

61 

62# Commented out and replaced with faster versions below 

63## def long2str(n): 

64## s='' 

65## while n>0: 

66## s=chr(n & 255)+s 

67## n=n>>8 

68## return s 

69 

70## import types 

71## def str2long(s): 

72## if type(s)!=types.StringType: return s # Integers will be left alone 

73## return reduce(lambda x,y : x*256+ord(y), s, 0L) 

74 

75def size (N): 

76 """size(N:long) : int 

77 Returns the size of the number N in bits. 

78 """ 

79 bits = 0 

80 while N >> bits: 

81 bits += 1 

82 return bits 

83 

84def getRandomNumber(N, randfunc=None): 

85 """Deprecated. Use getRandomInteger or getRandomNBitInteger instead.""" 

86 warnings.warn("Crypto.Util.number.getRandomNumber has confusing semantics"+ 

87 "and has been deprecated. Use getRandomInteger or getRandomNBitInteger instead.", 

88 GetRandomNumber_DeprecationWarning) 

89 return getRandomNBitInteger(N, randfunc) 

90 

91def getRandomInteger(N, randfunc=None): 

92 """getRandomInteger(N:int, randfunc:callable):long 

93 Return a random number with at most N bits. 

94 

95 If randfunc is omitted, then Random.new().read is used. 

96 

97 This function is for internal use only and may be renamed or removed in 

98 the future. 

99 """ 

100 if randfunc is None: 

101 _import_Random() 

102 randfunc = Random.new().read 

103 

104 S = randfunc(N>>3) 

105 odd_bits = N % 8 

106 if odd_bits != 0: 

107 char = ord(randfunc(1)) >> (8-odd_bits) 

108 S = bchr(char) + S 

109 value = bytes_to_long(S) 

110 return value 

111 

112def getRandomRange(a, b, randfunc=None): 

113 """getRandomRange(a:int, b:int, randfunc:callable):long 

114 Return a random number n so that a <= n < b. 

115 

116 If randfunc is omitted, then Random.new().read is used. 

117 

118 This function is for internal use only and may be renamed or removed in 

119 the future. 

120 """ 

121 range_ = b - a - 1 

122 bits = size(range_) 

123 value = getRandomInteger(bits, randfunc) 

124 while value > range_: 

125 value = getRandomInteger(bits, randfunc) 

126 return a + value 

127 

128def getRandomNBitInteger(N, randfunc=None): 

129 """getRandomInteger(N:int, randfunc:callable):long 

130 Return a random number with exactly N-bits, i.e. a random number 

131 between 2**(N-1) and (2**N)-1. 

132 

133 If randfunc is omitted, then Random.new().read is used. 

134 

135 This function is for internal use only and may be renamed or removed in 

136 the future. 

137 """ 

138 value = getRandomInteger (N-1, randfunc) 

139 value |= 2 ** (N-1) # Ensure high bit is set 

140 assert size(value) >= N 

141 return value 

142 

143def GCD(x,y): 

144 """GCD(x:long, y:long): long 

145 Return the GCD of x and y. 

146 """ 

147 x = abs(x) ; y = abs(y) 

148 while x > 0: 

149 x, y = y % x, x 

150 return y 

151 

152def inverse(u, v): 

153 """inverse(u:long, v:long):long 

154 Return the inverse of u mod v. 

155 """ 

156 u3, v3 = int(u), int(v) 

157 u1, v1 = 1, 0 

158 while v3 > 0: 

159 q=divmod(u3, v3)[0] 

160 u1, v1 = v1, u1 - v1*q 

161 u3, v3 = v3, u3 - v3*q 

162 while u1<0: 

163 u1 = u1 + v 

164 return u1 

165 

166# Given a number of bits to generate and a random generation function, 

167# find a prime number of the appropriate size. 

168 

169def getPrime(N, randfunc=None): 

170 """getPrime(N:int, randfunc:callable):long 

171 Return a random N-bit prime number. 

172 

173 If randfunc is omitted, then Random.new().read is used. 

174 """ 

175 if randfunc is None: 

176 _import_Random() 

177 randfunc = Random.new().read 

178 

179 number=getRandomNBitInteger(N, randfunc) | 1 

180 while (not isPrime(number, randfunc=randfunc)): 

181 number=number+2 

182 return number 

183 

184 

185def _rabinMillerTest(n, rounds, randfunc=None): 

186 """_rabinMillerTest(n:long, rounds:int, randfunc:callable):int 

187 Tests if n is prime. 

188 Returns 0 when n is definitly composite. 

189 Returns 1 when n is probably prime. 

190 Returns 2 when n is definitly prime. 

191 

192 If randfunc is omitted, then Random.new().read is used. 

193 

194 This function is for internal use only and may be renamed or removed in 

195 the future. 

196 """ 

197 # check special cases (n==2, n even, n < 2) 

198 if n < 3 or (n & 1) == 0: 

199 return n == 2 

200 # n might be very large so it might be beneficial to precalculate n-1 

201 n_1 = n - 1 

202 # determine m and b so that 2**b * m = n - 1 and b maximal 

203 b = 0 

204 m = n_1 

205 while (m & 1) == 0: 

206 b += 1 

207 m >>= 1 

208 

209 tested = [] 

210 # we need to do at most n-2 rounds. 

211 for i in range (min (rounds, n-2)): 

212 # randomly choose a < n and make sure it hasn't been tested yet 

213 a = getRandomRange (2, n, randfunc) 

214 while a in tested: 

215 a = getRandomRange (2, n, randfunc) 

216 tested.append (a) 

217 # do the rabin-miller test 

218 z = pow (a, m, n) # (a**m) % n 

219 if z == 1 or z == n_1: 

220 continue 

221 composite = 1 

222 for r in range (b): 

223 z = (z * z) % n 

224 if z == 1: 

225 return 0 

226 elif z == n_1: 

227 composite = 0 

228 break 

229 if composite: 

230 return 0 

231 return 1 

232 

233def getStrongPrime(N, e=0, false_positive_prob=1e-6, randfunc=None): 

234 """getStrongPrime(N:int, e:int, false_positive_prob:float, randfunc:callable):long 

235 Return a random strong N-bit prime number. 

236 In this context p is a strong prime if p-1 and p+1 have at 

237 least one large prime factor. 

238 N should be a multiple of 128 and > 512. 

239 

240 If e is provided the returned prime p-1 will be coprime to e 

241 and thus suitable for RSA where e is the public exponent. 

242 

243 The optional false_positive_prob is the statistical probability 

244 that true is returned even though it is not (pseudo-prime). 

245 It defaults to 1e-6 (less than 1:1000000). 

246 Note that the real probability of a false-positive is far less. This is 

247 just the mathematically provable limit. 

248 

249 randfunc should take a single int parameter and return that 

250 many random bytes as a string. 

251 If randfunc is omitted, then Random.new().read is used. 

252 """ 

253 # This function was implemented following the 

254 # instructions found in the paper: 

255 # "FAST GENERATION OF RANDOM, STRONG RSA PRIMES" 

256 # by Robert D. Silverman 

257 # RSA Laboratories 

258 # May 17, 1997 

259 # which by the time of writing could be freely downloaded here: 

260 # http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.2713&rep=rep1&type=pdf 

261 

262 # Use the accelerator if available 

263 if _fastmath is not None: 

264 return _fastmath.getStrongPrime(int(N), int(e), false_positive_prob, 

265 randfunc) 

266 

267 if (N < 512) or ((N % 128) != 0): 

268 raise ValueError ("bits must be multiple of 128 and > 512") 

269 

270 rabin_miller_rounds = int(math.ceil(-math.log(false_positive_prob)/math.log(4))) 

271 

272 # calculate range for X 

273 # lower_bound = sqrt(2) * 2^{511 + 128*x} 

274 # upper_bound = 2^{512 + 128*x} - 1 

275 x = (N - 512) >> 7; 

276 # We need to approximate the sqrt(2) in the lower_bound by an integer 

277 # expression because floating point math overflows with these numbers 

278 lower_bound = divmod(14142135623730950489 * (2 ** (511 + 128*x)), 

279 10000000000000000000)[0] 

280 upper_bound = (1 << (512 + 128*x)) - 1 

281 # Randomly choose X in calculated range 

282 X = getRandomRange (lower_bound, upper_bound, randfunc) 

283 

284 # generate p1 and p2 

285 p = [0, 0] 

286 for i in (0, 1): 

287 # randomly choose 101-bit y 

288 y = getRandomNBitInteger (101, randfunc) 

289 # initialize the field for sieving 

290 field = [0] * 5 * len (sieve_base) 

291 # sieve the field 

292 for prime in sieve_base: 

293 offset = y % prime 

294 for j in range ((prime - offset) % prime, len (field), prime): 

295 field[j] = 1 

296 

297 # look for suitable p[i] starting at y 

298 result = 0 

299 for j in range(len(field)): 

300 composite = field[j] 

301 # look for next canidate 

302 if composite: 

303 continue 

304 tmp = y + j 

305 result = _rabinMillerTest (tmp, rabin_miller_rounds) 

306 if result > 0: 

307 p[i] = tmp 

308 break 

309 if result == 0: 

310 raise RuntimeError ("Couln't find prime in field. " 

311 "Developer: Increase field_size") 

312 

313 # Calculate R 

314 # R = (p2^{-1} mod p1) * p2 - (p1^{-1} mod p2) * p1 

315 tmp1 = inverse (p[1], p[0]) * p[1] # (p2^-1 mod p1)*p2 

316 tmp2 = inverse (p[0], p[1]) * p[0] # (p1^-1 mod p2)*p1 

317 R = tmp1 - tmp2 # (p2^-1 mod p1)*p2 - (p1^-1 mod p2)*p1 

318 

319 # search for final prime number starting by Y0 

320 # Y0 = X + (R - X mod p1p2) 

321 increment = p[0] * p[1] 

322 X = X + (R - (X % increment)) 

323 while 1: 

324 is_possible_prime = 1 

325 # first check candidate against sieve_base 

326 for prime in sieve_base: 

327 if (X % prime) == 0: 

328 is_possible_prime = 0 

329 break 

330 # if e is given make sure that e and X-1 are coprime 

331 # this is not necessarily a strong prime criterion but useful when 

332 # creating them for RSA where the p-1 and q-1 should be coprime to 

333 # the public exponent e 

334 if e and is_possible_prime: 

335 if e & 1: 

336 if GCD (e, X-1) != 1: 

337 is_possible_prime = 0 

338 else: 

339 if GCD (e, divmod((X-1),2)[0]) != 1: 

340 is_possible_prime = 0 

341 

342 # do some Rabin-Miller-Tests 

343 if is_possible_prime: 

344 result = _rabinMillerTest (X, rabin_miller_rounds) 

345 if result > 0: 

346 break 

347 X += increment 

348 # abort when X has more bits than requested 

349 # TODO: maybe we shouldn't abort but rather start over. 

350 if X >= 1 << N: 

351 raise RuntimeError ("Couln't find prime in field. " 

352 "Developer: Increase field_size") 

353 return X 

354 

355def isPrime(N, false_positive_prob=1e-6, randfunc=None): 

356 """isPrime(N:long, false_positive_prob:float, randfunc:callable):bool 

357 Return true if N is prime. 

358 

359 The optional false_positive_prob is the statistical probability 

360 that true is returned even though it is not (pseudo-prime). 

361 It defaults to 1e-6 (less than 1:1000000). 

362 Note that the real probability of a false-positive is far less. This is 

363 just the mathematically provable limit. 

364 

365 If randfunc is omitted, then Random.new().read is used. 

366 """ 

367 if _fastmath is not None: 

368 return _fastmath.isPrime(int(N), false_positive_prob, randfunc) 

369 

370 if N < 3 or N & 1 == 0: 

371 return N == 2 

372 for p in sieve_base: 

373 if N == p: 

374 return 1 

375 if N % p == 0: 

376 return 0 

377 

378 rounds = int(math.ceil(-math.log(false_positive_prob)/math.log(4))) 

379 return _rabinMillerTest(N, rounds, randfunc) 

380 

381 

382# Improved conversion functions contributed by Barry Warsaw, after 

383# careful benchmarking 

384 

385import struct 

386 

387def long_to_bytes(n, blocksize=0): 

388 """long_to_bytes(n:long, blocksize:int) : string 

389 Convert a long integer to a byte string. 

390 

391 If optional blocksize is given and greater than zero, pad the front of the 

392 byte string with binary zeros so that the length is a multiple of 

393 blocksize. 

394 """ 

395 # after much testing, this algorithm was deemed to be the fastest 

396 s = b('') 

397 n = int(n) 

398 pack = struct.pack 

399 while n > 0: 

400 s = pack('>I', n & 0xffffffff) + s 

401 n = n >> 32 

402 # strip off leading zeros 

403 for i in range(len(s)): 

404 if s[i] != b('\000')[0]: 

405 break 

406 else: 

407 # only happens when n == 0 

408 s = b('\000') 

409 i = 0 

410 s = s[i:] 

411 # add back some pad bytes. this could be done more efficiently w.r.t. the 

412 # de-padding being done above, but sigh... 

413 if blocksize > 0 and len(s) % blocksize: 

414 s = (blocksize - len(s) % blocksize) * b('\000') + s 

415 return s 

416 

417def bytes_to_long(s): 

418 """bytes_to_long(string) : long 

419 Convert a byte string to a long integer. 

420 

421 This is (essentially) the inverse of long_to_bytes(). 

422 """ 

423 acc = 0 

424 unpack = struct.unpack 

425 length = len(s) 

426 if length % 4: 

427 extra = (4 - length % 4) 

428 s = b('\000') * extra + s 

429 length = length + extra 

430 for i in range(0, length, 4): 

431 acc = (acc << 32) + unpack('>I', s[i:i+4])[0] 

432 return acc 

433 

434# For backwards compatibility... 

435import warnings 

436def long2str(n, blocksize=0): 

437 warnings.warn("long2str() has been replaced by long_to_bytes()") 

438 return long_to_bytes(n, blocksize) 

439def str2long(s): 

440 warnings.warn("str2long() has been replaced by bytes_to_long()") 

441 return bytes_to_long(s) 

442 

443def _import_Random(): 

444 # This is called in a function instead of at the module level in order to 

445 # avoid problems with recursive imports 

446 global Random, StrongRandom 

447 from Crypto import Random 

448 from Crypto.Random.random import StrongRandom 

449 

450 

451 

452# The first 10000 primes used for checking primality. 

453# This should be enough to eliminate most of the odd 

454# numbers before needing to do a Rabin-Miller test at all. 

455sieve_base = ( 

456 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 

457 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 

458 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 

459 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 

460 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 

461 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 

462 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 

463 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 

464 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 

465 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 

466 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 

467 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 

468 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 

469 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 

470 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 

471 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 

472 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 

473 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 

474 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 

475 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 

476 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 

477 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 

478 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 

479 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 

480 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 

481 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 

482 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 

483 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 

484 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 

485 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 

486 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 

487 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 

488 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 

489 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 

490 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 

491 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 

492 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 

493 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 

494 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 

495 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 

496 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 

497 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 

498 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 

499 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 

500 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 

501 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 

502 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 

503 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 

504 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 

505 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 

506 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 

507 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 

508 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 

509 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 

510 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 

511 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 

512 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 

513 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 

514 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 

515 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 

516 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 

517 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 

518 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 

519 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 

520 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 

521 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 

522 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 

523 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 

524 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 

525 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 

526 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 

527 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 

528 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 

529 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 

530 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 

531 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 

532 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 

533 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 

534 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 

535 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 

536 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 

537 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 

538 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 

539 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 

540 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 

541 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 

542 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 

543 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 

544 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 

545 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 

546 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 

547 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 

548 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 

549 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 

550 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 

551 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 

552 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 

553 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 

554 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 

555 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 

556 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 

557 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 

558 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 

559 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 

560 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 

561 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 

562 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 

563 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 

564 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 

565 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 

566 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 

567 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 

568 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 

569 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 

570 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 

571 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 

572 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 

573 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 

574 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 

575 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 

576 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 

577 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 

578 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007, 

579 10009, 10037, 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 

580 10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163, 10169, 10177, 

581 10181, 10193, 10211, 10223, 10243, 10247, 10253, 10259, 10267, 10271, 

582 10273, 10289, 10301, 10303, 10313, 10321, 10331, 10333, 10337, 10343, 

583 10357, 10369, 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459, 

584 10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531, 10559, 10567, 

585 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639, 10651, 10657, 

586 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733, 10739, 

587 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859, 

588 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949, 

589 10957, 10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059, 

590 11069, 11071, 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149, 

591 11159, 11161, 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251, 

592 11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317, 11321, 11329, 

593 11351, 11353, 11369, 11383, 11393, 11399, 11411, 11423, 11437, 11443, 

594 11447, 11467, 11471, 11483, 11489, 11491, 11497, 11503, 11519, 11527, 

595 11549, 11551, 11579, 11587, 11593, 11597, 11617, 11621, 11633, 11657, 

596 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731, 11743, 11777, 

597 11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831, 11833, 

598 11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933, 

599 11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 

600 12037, 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109, 

601 12113, 12119, 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211, 

602 12227, 12239, 12241, 12251, 12253, 12263, 12269, 12277, 12281, 12289, 

603 12301, 12323, 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401, 

604 12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473, 12479, 12487, 

605 12491, 12497, 12503, 12511, 12517, 12527, 12539, 12541, 12547, 12553, 

606 12569, 12577, 12583, 12589, 12601, 12611, 12613, 12619, 12637, 12641, 

607 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739, 

608 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 12829, 

609 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923, 

610 12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 

611 13009, 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 

612 13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187, 

613 13217, 13219, 13229, 13241, 13249, 13259, 13267, 13291, 13297, 13309, 

614 13313, 13327, 13331, 13337, 13339, 13367, 13381, 13397, 13399, 13411, 

615 13417, 13421, 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499, 

616 13513, 13523, 13537, 13553, 13567, 13577, 13591, 13597, 13613, 13619, 

617 13627, 13633, 13649, 13669, 13679, 13681, 13687, 13691, 13693, 13697, 

618 13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759, 13763, 13781, 

619 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877, 13879,