# import random from itertools import combinations import math def eucli

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151``` ```import random from itertools import combinations import math def euclid(a, b): """returns the Greatest Common Divisor of a and b""" a = abs(a) b = abs(b) if a < b: a, b = b, a while b != 0: a, b = b, a % b return a def coPrime(l): """returns 'True' if the values in the list L are all co-prime otherwise, it returns 'False'. """ for i, j in combinations(l, 2): if euclid(i, j) != 1: return False return True def extractTwos(m): """m is a positive integer. A tuple (s, d) of integers is returned such that m = (2 ** s) * d.""" # the problem can be break down to count how many '0's are there in # the end of bin(m). This can be done this way: m & a stretch of '1's # which can be represent as (2 ** n) - 1. assert m >= 0 i = 0 while m & (2 ** i) == 0: i += 1 return i, m >> i def int2baseTwo(x): """x is a positive integer. Convert it to base two as a list of integers in reverse order as a list.""" # repeating x >>= 1 and x & 1 will do the trick assert x >= 0 bitInverse = [] while x != 0: bitInverse.append(x & 1) x >>= 1 return bitInverse def modExp(a, d, n): """returns a ** d (mod n)""" assert d >= 0 assert n >= 0 base2D = int2baseTwo(d) base2DLength = len(base2D) modArray = [] result = 1 for i in range(1, base2DLength + 1): if i == 1: modArray.append(a % n) else: modArray.append((modArray[i - 2] ** 2) % n) for i in range(0, base2DLength): if base2D[i] == 1: result *= base2D[i] * modArray[i] return result % n def millerRabin(n, k): """ Miller Rabin pseudo-prime test return True means likely a prime, (how sure about that, depending on k) return False means definitely a composite. Raise assertion error when n, k are not positive integers and n is not 1 """ assert n >= 1 # ensure n is bigger than 1 assert k > 0 # ensure k is a positive integer so everything down here makes sense if n == 2: return True # make sure to return True if n == 2 if n % 2 == 0: return False # immediately return False for all the even numbers bigger than 2 extract2 = extractTwos(n - 1) s = extract2[0] d = extract2[1] assert 2 ** s * d == n - 1 def tryComposite(a): """Inner function which will inspect whether a given witness will reveal the true identity of n. Will only be called within millerRabin""" x = modExp(a, d, n) if x == 1 or x == n - 1: return None else: for j in range(1, s): x = modExp(x, 2, n) if x == 1: return False elif x == n - 1: return None return False for i in range(0, k): a = random.randint(2, n - 2) if tryComposite(a) == False: return False return True # actually, we should return probably true. def primeSieve(k): """return a list with length k + 1, showing if list[i] == 1, i is a prime else if list[i] == 0, i is a composite, if list[i] == -1, not defined""" def isPrime(n): """return True is given number n is absolutely prime, return False is otherwise.""" for i in range(2, int(n ** 0.5) + 1): if n % i == 0: return False return True result = [-1] * (k + 1) for i in range(2, int(k + 1)): if isPrime(i): result[i] = 1 else: result[i] = 0 return result def findAPrime(a, b, k): """Return a pseudo prime number roughly between a and b, (could be larger than b). Raise ValueError if cannot find a pseudo prime after 10 * ln(x) + 3 tries. """ x = random.randint(a, b) for i in range(0, int(10 * math.log(x) + 3)): if millerRabin(x, k): return x else: x += 1 raise ValueError ```