def is_prime_big(n, prec=1000):
    if n < 2:
        return False

    if n % 2 == 0:
        return n == 2

    # this means n is odd
    d = n - 1
    exp = 0
    while d % 2 == 0:
        d /= 2
        exp += 1

    # n - 1=d*(2**exp)
    count = 0
    while count < prec:
        a = random.randint(2, n - 1)
        b = bin_exp_mod(a, d, n)
        if b != 1:
            flag = True
            for _ in range(exp):
                if b == n - 1:
                    flag = False
                    break
                b = b * b
                b %= n
            if flag:
                return False
            count += 1
    return True