code: def miller_rabin(n, k):
      
      assert n > 3
  
      # find r and d such that n-1 = 2^r × d
      d = n-1
      r = 0
      while d % 2 == 0:
          d //= 2
          r += 1
      assert n-1 == d * 2**r
      assert d % 2 == 1
  
      for _ in range(k):  # each iteration divides risk of false prime by 4
          a = random.randint(2, n-2)  # choose a random witness
  
          x = pow(a, d, n)
          if x == 1 or x == n-1:
              continue  # go to next witness
  
          for _ in range(1, r):
              x = x*x % n
              if x == n-1:
                  break   # go to next witness
          else:
              return False
      return True
docs: Run the Miller-Rabin test on n with at most k iterations
  
      Arguments:
          n (int): number whose primality is to be tested
          k (int): maximum number of iterations to run
  
      Returns:
          bool: If n is prime, then True is returned. Otherwise, False is
          returned, except with probability less than 4**-k.
  
      See <https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test>