# Challenge 1 - gcd def gcd(a: int, b: int) -> int: while b != 0: r = a % b a = b b = r return a # Challenge 2 - extended Euclidean algorithm def extended_gcd(a: int, b: int) -> (int, int, int): """ Args: a: an integer b: an integer Returns: (gcd, u, v) so that u*a + v*b = gcd """ u = [1, 0] v = [0, 1] while b != 0: r = a % b q = a // b u.append(u[-2] - u[-1] * q) v.append(v[-2] - v[-1] * q) a = b b = r return a, u[-2], v[-2] # Challenge 6 - quadratic residues def quadratic_residue(N: int, x: int): """Find the quadratic residue of x mod N. Args: N: a prime integer x: the integer for which we look for a quadratic residue. Returns: Either none or the square root of x mod N. """ for i in range(N): if pow(i, 2, N) == x: return i return None # Challenge 7 - Legendre's symbol def _is_quadratic_residue(x: int, N: int) -> bool: if pow(x, (N - 1) // 2, N) == 1: return True return False def legendre_symbol(N: int, candidates: [int]): """Find the square root of x mod N using Legendre's symbol. Args: N: a prime integer. x: a list of integer that may be quadratic residues. Returns: The square root of the first element in x which is a quadratic residue. """ for x in candidates: if _is_quadratic_residue(x, N): # TODO find the square root of x mod N try: return tonelli_shanks(x, N) except: return None return None # Challenge 8 - tonelli-shanks def tonelli_shanks(x, p): q = p - 1 k = 0 while q % 2 == 0: q = q // 2 k += 1 if q % 2 == 0: raise ValueError z = 1 while _is_quadratic_residue(z, p): z += 1 c, t, r = pow(z, q, p), pow(x, q, p), pow(x, (q + 1) // 2, p) while True: if t == 0: return 0 if t == 1: return r i = 1 while i < k: if pow(t, 1 << i, p) == 1: break i += 1 b = pow(c, 1 << (k - i - 1), p) k = i c = pow(b, 2, p) t = t * pow(b, 2) % p r = r * b % p